60. Permutation Sequence

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

此题虽然在分类上属于backtracking，但如果直接利用回溯法求全排列又会造成在n较大的情况下超时，所以不能直接利用回溯法，而是需要分析其中的规律，从而直接构造出排列。

假设

n=4

则全排列有

4*3*2*1=24

种可能性，设此时

k=17

因为以1,2开头的排列只有

3*2*1*2=12

种

恰好小于17，所以可以确定所求排列的开头必然是3在确定开头为3之后，将其从原字符串中删除，还剩下

17-12=5

种排列，字符串中还剩下124,以上述方法确定第二个元素为4,重复上述过程，直到得出所求排列即可。

代码如下:

code

class Solution {
private:
    int fact(int n){
        int res=1;
        for(int i=2;i<=n;i++)
            res=res*i;
        return res;
    }
    char helper(string & s, int & k){
        int temp=fact(s.size()-1),i=(k-1)/temp;
        char res=s[i];
        s.erase(i,1);
        k=k-i*temp;
        return res;
    }
public:
    string getPermutation(int n, int k) {
        string s=string("123456789").substr(0,n);
        string res(n,' ');
        for(int i=0;i<n;i++)
            res[i]=helper(s,k);
        return res;
    }
};