LeetCode 60. Permutation Sequence

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 60. Permutation Sequence 原题链接中等

作者：

yxc , 2018-04-27 00:56:28 , 所有人可见 , 阅读 3122

11

6

题目描述

集合 $[1, 2, 3, …, n]$ 总共有 $n!$ 个不同的排列。
当 $n=3$ 时，将全排列排好序，会得到如下结果：

“123”
“132”
“213”
“231”
“312”
“321”

给出 $n$ 和 $k$, 请返回第 $k^{th}$ 个排列。

样例1

输入：n = 3, k = 3
输出："213"

样例2

输入：n = 4, k = 9
输出："2314"

算法

(计数) $O(n^2)$

做法：

从高位到低位依次考虑每一位；
对于每一位，从小到大依次枚举未使用过的数，确定当前位是几；

为了便于理解，我们这里给出一个例子的具体操作：$n = 4, k = 14$。
首先我们将所有排列按首位分组：

1 + (2, 3, 4的全排列)
2 + (1, 3, 4的全排列)
3 + (1, 2, 4的全排列)
4 + (2, 3, 4的全排列)

接下来我们确定第 $k = 14$ 个排列在哪一组中。每组的排列个数是 $3! = 6$ 个，所以第14个排列在第3组中，所以首位已经可以确定，是3。

然后我们再将第3组的排列继续分组：

31 + (2, 4的全排列)
32 + (1, 4的全排列)
34 + (1, 2的全排列)

接下来我们判断第 $k = 14$ 个排列在哪个小组中。我们先求第 $14$ 个排列在第三组中排第几，由于前两组每组有6个排列，所以第14个排列在第3组排第 $14 - 6 * 2 = 2$。
在第三组中每个小组的排列个数是 $2! = 2$个，所以第 $k$ 个排列在第1个小组，所以可以确定它的第二位数字是1。

依次类推，可以推出第14个排列是 3142。

时间复杂度分析：两重循环，所以时间复杂度是 $O(n^2)$。

C++ 代码

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        vector<bool> st(n);

        for (int i = 0; i < n; i ++ ) {
            int f = 1;
            for (int j = 1; j < n - i; j ++ ) f *= j;
            for (int j = 0; j < n; j ++ ) {
                if (!st[j]) {
                    if (k <= f) {
                        res += to_string(j + 1);
                        st[j] = true;
                        break;
                    }
                    k -= f;
                }
            }
        }

        return res;
    }
};

7 评论

GinSoda 2021-08-08 20:26

/*
思路：逆康托展开
decontar(n=5, k=62)
k = k - 1 //序数从0开始
取值范围为n!
想象61在[0, 119]排第几位，而非62在[1, 120]中排第几位。
因为余数的取值范围是[0, n!-1], 商的取值范围是[0, n-1]
范围取为[0, n!-1]，时余数为0也具有含义，和余数取值范围天然对应。
而范围取为[1, n!]时，余数为0需要特殊处理。
这也是为什么康托展开取值范围是从0开始

确定第一位，每位对应(n-1)!=4!种情况，
61 / 4! = 2余13 //商为2, 所以61属于第3组，该位是rest[2]
确定第二位，在一位确定的情况下，k = 13
13 / 3! = 2余1
确定第三位，在二位确定的情况下，k = 1
1 / 2! = 0余1 //
确定第四位，在三位确定的情况下，k = 1
1 / 1! = 1余0
确定第五位，在四位确定的情况下，k = 0
0 / 0! = 0余0
quotient = {2, 2, 0, 1, 0}, remainder = {13, 1, 1, 0, 0}
rest = {1, 2, 3, 4, 5}, 按商的排列从rest中不放回的选取元素
ans = {rest[2], rest[2], rest[0], rest[1], rest[0]} = {3, 4, 1, 5, 2}
*/

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> fact(1,1), rest; // fact[i]代表i!, rest[i]当前第i位小的数
        string ans = ""; 
        int present = 1; //辅助构造fact[i]
        for(int i = 1; i <= n; i++) {
            rest.push_back(i);
            present *= i;
            fact.push_back(present);
        }
        k --; // 康托展开序数从0开始
        for (int i = n-1; i >= 0; i --) {
            int q = k / fact[i]; //商quotient
            int r = k % fact[i]; //余数remainder
            k = r; //更新下一位数对应的序数
            ans += to_string(rest[q]);
            rest.erase(rest.begin() + q); //对rest不放回的抽取
        }
        return ans;
    }
};

greg666 2019-04-13 12:49

其实还是O(n^2), 删除操作O(n)

greg666 2019-04-13 12:47

卧槽，我发现我O(n)了。

greg666 2019-04-13 12:46

根据yxc代码改编：

string getPermutation(int n, int k) {
    string str = "";
    int divisor = 1;
    for (int i = 0; i < n; i++) {
        str += to_string(i + 1);
        divisor *= 1 + i;
    }

    string res;
    for (int i = 0; i < n; i++) {
        divisor /= n - i;

        int index = k / divisor;
        k %= divisor;
        if (k == 0) {
            k = divisor;
            index-- ;
        }

        res += str[index];
        str.erase(str.begin() + index);
    }

    return res;
}