[C++] LeetCode 60. 第k個排列

題目

給出集合

[1,2,3,…,n]

，其所有元素共有

n!

種排列。

按大小順序列出所有排列情況，并一一标記，當

n = 3

時, 所有排列如下：

"123" "132" "213" "231" "312" "321"

給定

n

和

k

，傳回第

k

個排列。

說明：

給定

n

的範圍是

[1, 9]

。

給定

k

的範圍是

[1, n!]

。

示例 1:

輸入: n = 3, k = 3

輸出: “213”

示例 2:

輸入: n = 4, k = 9

輸出: “2314”

思路解析

這道題可以考慮從高位開始逐位确定該位應該為哪個數字。比如

n=4,k=3

時，

最高位為

1

則最多可以形成

3*2*1=6

種組合，大于

k

，是以最高位确定為

1

，第二位為

2

時最多有

2*1=2

種組合，小于

k

，而第二位為

3

的時候，則最多有

2*2*1=4

位，大于

k

，是以第二位為

3

，此時還需要形成

3%2=1

種，第三位為

2

時，隻有一種，故第三位是

2

，最後一位是

4

代碼

class Solution {
public:
    string getPermutation(int n, int k) {
        string nums;
        for(int i=1;i<=n;i++) nums+=i+'0';
        string res;
        vector<int> multi(n,1);
        for(int i=1;i<n;i++) multi[i]=multi[i-1]*i;
        for(int i=n-1;i>=0;--i){
            int a = k / multi[i];
            k = k % multi[i];
            if(k==0){
                res.push_back(nums[a-1]);
                nums.erase(a-1,1);
                reverse(nums.begin(),nums.end());
                res+=nums;
                return res;
            }
            else if(k==1){
                res.push_back(nums[a]);
                nums.erase(a,1);
                res+=nums;
                return res;
            }
            else{
                res.push_back(nums[a]);
                nums.erase(a,1);
            }
        }
        return res;
    }
};