LeetCode 60. 排列序列

LeetCode 60. 排列序列

思路1：

算出第k个排列是第几个数，计算当前分支的选择，比如第一个数选择1，那么下面的分支有23和32两种选择，所以是 1 * 2 = 2，因为k = 3，所以不会是当前的分支，更新k，然后去判断下一个分支。这样依次枚举每一位。

代码：

class Solution {
public:
    string getPermutation(int n, int k) {
        //依次确定n个数
        string res;
        vector<bool> st(n);
        for(int i = 0;i < n;i++){
            int fact=1;
            //计算阶乘 即当前位的下面有多少个选择
            for(int j=1;j<=n-i-1;j++) fact*=j;

            //算当前的分支的数
            for(int j = 1;j <= n;j++){
                if(!st[j]){
                    //如果第k个数不在当前的范围
                    if(fact < k) k-=fact;
                    //如果k在当前的范围内 就可以确定一个数了
                    else{
                        st[j]=true;
                        res+=to_string(j);
                        break;
                    }
                }
            }
        }
        return res;
    }
};

思路2：
使用STL的算法，next_permutation函数，返回当前序列的下一个排列。
next_permutation参考

代码：

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        int i=1;
        //第一个排列是 1 2 3
        while(i <= n) res.push_back((i++) + '0');
        for(int j=0;j<k-1;j++) next_permutation(res.begin(),res.end());
        return res;
    }
};