LeetCode60. 第k个排列

解法一：用next_permutation()函数，要求第k个排列，就从"123...n"开始调用 k - 1 次 next_permutation()函数即可。

class Solution {

public:

    string getPermutation(int n, int k) {

        string res;

        for(int i = 1; i <= n; ++i) {

            res += to_string(i);

        }

        for(int i = 0; i < k - 1; ++i) {

            next_permutation(res.begin(), res.end());

        }

        return res;

    }

};

解法二：

计数，计算第k个排列各个位的数字。

比如 n = 4, k = 10。假设我们确定了第0位（最高位）的数字，那么剩下三位有三种排列，即剩下(n - 1)! = 3! = 6种排列。

因此如果第 0 位填1，那么当前的排列范围为第1个排列到第6个排列，6 < 10，因此第一个数字不填1。

那么再假设第 0 位填2，这里显然跨过了第 0 位填 1 的6个排列，因此 k - (n - 1)! = 10 - 3 ! = 4，

又由于第 0 位填2的排列也有 3! = 6个，6 > 4，

因此我们可以确定第 10 个排列的第 0 位（第一个数字）填2。
然后就是要确定第 1 位（第二个数字），依旧是从小到大枚举：

假设第 1 位填 1，那么剩下没填的位数有两位，剩下的排列数就是 2! = 2， 2 < k (k现在是4）

因此第 1 位不是填1 ，跳过第 1 位填 1 的所有排列， k 再更新一下：k -= 2! ，现在 k 的值是 2。

那再假设第 1 位填 3 （由于2已经用过了，所以跳过 2），第 0 位填 2、第 1 位填 3 的排列数为 2, 2 >= k，

所以我们可以确定第 1 位填3。
现在枚举第 2 位（第三个数字）的情况，假设第 2 位填1，剩下只剩一位没填，排列数为 1， 1 < k (k的值是2）

所以跳过第 2 位为 1 的排列，更新k ： k -= 1! ， k现在为1，

由于2，3都已经用过了，所以跳过，假设第 2 位填 4：剩下的排列数为1， 1 >= k，

因此我们得到第 2 位数字为 4.
这样第 3 位（第四个数字，即最后一个）只能填我们还没有填的1.

所以我们知道了当 n 为 4 时，第10个排列的数字为 "2341"

根据上面的思路，得到如下代码：

class Solution {

public:

    string getPermutation(int n, int k) {

        string res;

        vector<bool> used(10);                 //used记录每个数字是否使用过

        for(int i = 0; i < n; ++i) {           //枚举每个位置填的数字，确定了 0 ~ n - 1位填的每个数字后就返回结果

            int fact = 1;                      //fact是剩下的位数可以组成的排列数，大小为 (n - i - 1)!

            for(int j = 1; j <= n - i - 1; ++j) {           //前面已经填了 i + 1位数，剩下的位存在的总排列数就是 (n - (i + 1))!

                fact *= j;

            }

            for(int j = 1; j<= n; ++j) {            //从小到大枚举当前位置可以填的数字

                if(used[j] == false) {              //当前位置只可以填没有用过的数字

                    if(fact < k) {                  //如果剩下的排列数小于 k ，说明第k个排列的第 i 个位置的数字不是 j（比 j 大）

                        k -= fact;                  //跳过第 i 位为 j 的所有排列，并更新 k

                    } else {

                        res += to_string(j);        //否则，说明第 k 个排列的第 i 个数字为 j

                        used[j] = true;             //记录数字 j 已经被使用过，后面的位置就不能再填 j 了

                        break;                      //已经确定了第 i 位的数字，跳出当前循环，继续判断 i + 1（下一位）的数字

                    }

                }

            }

        }

        return res;

    }

};

巴特西

LeetCode60. 第k个排列

最新文章

热门文章