题目

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.

分析

基本思路是按照类似于进制数的产生方法，实现排列方式与十进制数的一一对应关系。对于一个排列来说，每一位有不同的权重，第n位（从右往左）的权重为(n-1)!，第n位的数字大小则为该位元素处于目前所剩余的待排列数字中的序号。

实现

class Solution {
public:
    string getPermutation(int n, int k) {
        int tmp[n+1], flag[n+1];
        tmp[0] = 1; flag[0] = false;
        for(int i=1; i<n+1; i++){
            tmp[i] = tmp[i-1] * i;
            flag[i] = false;
        }
        string ans;
        for(int i=n; i>=1; i--){
            int m, j, t;
            m = k / tmp[i-1] + (k%tmp[i-1]==0 ? 0 : 1);
            k %= tmp[i-1];
            k = k==0 ? tmp[i-1] : k;
            for(j=1, t=0; j<n+1; j++){
                if(flag[j]) continue;
                t++;
                if(t==m){
                    flag[j] = true;
                    break;
                }
            }
            ans += j + '0';
        }
        return ans;
    }
};