学步园

The set [1,2,3,…,n] contains a total of n!
unique permutations.

By listing and labeling all of the permutations in order,

We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

思路：这道题我刚开始做的时候，是将这n个数全排列，然后得到第k个数列，毫无疑问，超时。后来我想到其实可以找到规律的，例如n=3,k=5，对1,2,3进行全排列，当第一个数固定时，第二个和第三个位置有A(2,2)种排法，所以5=2A(2,2)+A(1,1)。然后将这个问题抽象成k=a1*f(n-1)+a2*f(n-2)+...an*f(0)，ai表示第i个位置从1到n的变化次数，并且used[k]没有参与a1..a(i-1)的全排列。然后可以AC了。

class Solution {
public:
    string getPermutation(int n, int k) {
       int factor[10];
       int i;
       int a[n],seq[n],used[n+1];
       memset(a,0,sizeof(a));
       memset(used,0,sizeof(used));
       factor[0] = 1;
       for(i=1; i<=9; ++i)
       {
           factor[i] = factor[i-1] * i;
       }  
       string res = "";
       if (k > factor[n])
       {
           return res;
       }   
       k = k - 1;    
       for(i=0; i<n; ++i)
       {
           a[i] = k / factor[n-i-1];
           k -= a[i]*factor[n-i-1];
       }    
       for(i=0; i<n; ++i)
       {
           int co = 0;
           while(a[i] >= 0)
           {
               ++co;
               if(used[co] == 0)
               {
                   a[i]--;
               }    
           }  
           used[co] = 1;
           res += (co+'0');  
       }       
       return res; 
    }
};