Permutation Sequence

Permutation Sequence

Total Accepted: 44618 Total Submissions: 187104 Difficulty: Medium

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=4,k=8

1.固定第0个位置后面有3！=6中排列，

2.固定第0,1个位置后面有2！=2中排列

pos: 0      1      2       3

       3！    2！   1！    0

第0个位置每固定一个字符，后面就有6种排列，所以第0个位置分别为'1','2','3','4'时分别对应的排列的范围是：

序号     字符        范围

 0         '1'         第1-6个排序

 1         '2'         第7-12个排列

 2         '3'         第13-18个排列

 3         '4'         第19-24个排列

k=8 属于第7-12个排列，其实就是(k-1)/6个序号的排列

排好第0个位置的字符后，按同样的方法排第1个位置就可以了，此时，k=k%6=8%6=2;

class Solution {
public:
    string getPermutation(int n, int k) {
        
        string s;
        int fact = 1;
        
        for(int i=1;i<=n;i++){
            s.push_back(i+'0');
            fact *= i;
        }
        
        k--;
        
        string res
        
        while(n){
            fact /= n;
            int pos = k/fact;
            res.push_back(s[pos]);
            s.erase(s.begin()+pos);
            k = k%fact;
            --n;
        }
        
        return res;
    }
};