[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;
    }
};