Permutation Sequence

时间：2015-05-28 22:45:24 收藏：0 阅读：306

解法参考了：http://blog.csdn.net/lanxu_yy/article/details/17261527

思路：

思路1是用NP的方式来罗列出所有的排列再找出第k个结果，这种方法的时间复杂度与空间复杂度比较高。思路2是研究排序结果的规律，例如取n是，结果可以分为n个组，第一组是第一个数字取最小的那个（即1），第k组是取数字排第k小的那个（即k），每组的数字个数是(n-1)!。依次类推可以递归到n为1时。最终k可以表示为k=A1(n-1)!+A2(n-2)!+...+An，其中Ak代表该数为剩余数字中第Ak小的数字。

例如，n=3，k=5时，我们首先将k换算成4（第一个元素为0而不是1），由于(n-1)!=2，所以第一个元素应该是第4/2=2小的元素。第二个元素的k=4%2=0，且(n-1)!=1，所以第二个元素应该是第0小的元素。第三个元素的k=0%1=0，且(n-1)!=1，所以第三个元素应该是第0小元素。一开始的数字为（1，2，3）第一位是第2（0表示第一位）小元素，故取3，第二位是剩余数字（1，2）中第0小的元素，即为1，第三位是剩余数字（2）中第0小的元素，即2。所以结果为312。

我刚开始用的就是思路一的方法，结果测试不通过，运行超时，换成思路二的就好了，注意代码27行的break，不然代码就错了。其实感觉这道题和算法关系不大，完全就是在考数学。

 1 class Solution {
 2 public:
 3     string getPermutation(int n, int k) {
 4        vector<bool> flag(n,false);
 5        int *A=new int[n];
 6        int base=1;
 7        for(int i=2;i<n;i++)
 8             base*=i;
 9        int sum=k-1;
10        for(int i=0;i<n;i++)
11        {
12            A[i]=sum/base;
13            sum=sum%base;
14            if(base!=1)  
15                 base=base/(n-1-i);
16        }
17        string str;
18        for(int i=0;i<n;i++)
19         for(int j=0;j<n;j++)
20         {
21             if(!flag[j])
22             {
23                 if(A[i]==0)
24                 {
25                     str.push_back(j+‘1‘);
26                     flag[j]=true;
27                     break;
28                 }
29                 else
30                 {
31                     A[i]--;
32                 }
33             }
34         }
35         return str;
36     }
37 };

原文：http://www.cnblogs.com/qiaozhoulin/p/4536986.html