LeetCode Permutation Sequence

Permutation Sequence

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.

   本题最直接的算法就是，一个一个permutation的产生，然后数到k就是答案了，但是这样的程序很慢，高手是不能这样写程序的。O(∩_∩)O~

   其实这类题有个很特别的方法做的，不过没看过的话，就很难想出来了。

   可以参考下面博客，求一个数列的全部全排列。而不同的就是这里只是求某个特定的全排列。

   http://blog.csdn.net/kenden23/article/details/17166105
   

   使用上面博客中的最后一个方法，定位下标的方法就可以写出很快的程序了。

   下面程序8ms都可以过，我分了几个函数，希望可以清晰一点吧。

   class Solution {
   public:
       string getPermutation(int n, int k) {
   		vector
       
         bound = generatBound(n);
   		vector
        
          table = converNumToTable(bound, n, k); return permuteK(n, k, bound, table); } string permuteK(int n, int k, vector
         
           &bound, vector
          
            &table) { vector
           
             num(n); string res; for (int i = 1; i <= n; i++) { num[i-1] = i; } for (int j = 0; j < n; j++) { res.push_back(num[table[j]] + '0'); num.erase(num.begin()+table[j]); } return res; } vector
            
              converNumToTable(vector
             
               &bound, int n, int num) { vector
              
                table(n); num--; for (int i = n-2; i>=0 && num > 0; i--) { table[i] = num % (bound[i]+1); num /= (bound[i]+1); } return table; } vector
               
                 generatBound(int n) { vector
                
                  bound(n); for (int i = 0; i < n; i++) { bound[i] = n-1-i; } return bound; } };