Permutation Sequence (Medium)

Description

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):
“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

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

Analysis

康托展开。。好像是叫这个？还是当初hcbbt巨巨教我的。。orz

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//C++
class Solution {
    string ans;
public:
    string getPermutation(int n, int k) {
        k--;
        int fac[10] = {1,1},num[10]={0,1};
        for(int i = 2;i<=9;i++){
            fac[i] = i*fac[i-1];
            num[i] = i;
        }
        for(int i = 1;i<=n;i++){
            int divd = k/fac[n-i]+1;
            k = k%fac[n-i];
            int cnt = 0;
            for(int j=1;j<=9;j++)
            {
                if(num[j]!=-1)
                    cnt++;
                if(cnt==divd){
                    ans+=(num[j]+'0');
                    num[j] = -1;
                    break;
                }
            }
        }
        return ans;
    }
};