【经典算法题】排列序列

Leetcode 0060 排列序列

题目描述：Leetcode 0060 排列序列

分析

• 本题的考点：数学。

• 对于c++而言，可以使用next_permutation，计算量为$n!\times n$，最大为$9!\times 9=3,265,920$，可以通过，考试肯定用这种做法。

• 下面讲解另一种做法：计数法。

• 对于n，我们要求第k大的小的数，我们可以依次考虑1~n这些位置应该放入哪个数字，从第一个位置开始考虑，如果放入1的话，则后面还有n-1个位置，一共有(n-1)!种方案，比较k和(n-1)!的大小，如果k > (n-1)!，说明第k小的数必定不可能是1开头的数字。之后将k更新为k-(n-1)!，考虑第一个位置放入2，直到找到第一个位置放置的数字，使得$k\le (n-1)!$，则该数字就是第一位应该放的数字。

• 依次考虑后面2~n位应该放入哪些数字。注意已经用过的数字不能再使用，需要使用一个数组st进行判重。

• 如下图，是n=4, k=10对应的情况：

代码

• C++

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

class Solution {
public:string getPermutation(int n, int k) {vector<int> fact(10, 1);  // 阶乘for (int i = 2; i < 10; i++) fact[i] = fact[i - 1] * i;string res;vector<bool> st(10);  // 判重数组for (int i = 0; i < n; i++)  // 枚举每个位置, 即res[i]应该填入哪个数字for (int j = 1; j <= n; j++)  // 枚举所有数字if (!st[j]) {  // j还没被使用过if (fact[n - 1 - i] < k)   // 说明res[i]不应该放入jk -= fact[n - 1 - i];else {res += to_string(j);st[j] = true;break;  // 表示res[i]已经填入了正确的数字}}return res;}
};

• Java

class Solution {public String getPermutation(int n, int k) {int[] fact = new int[n];fact[0] = 1;for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i;StringBuilder sb = new StringBuilder();boolean[] st = new boolean[10];for (int i = 0; i < n; i++)for (int j = 1; j <= n; j++)if (!st[j]) {if (fact[n - 1 - i] < k) k -= fact[n - 1 - i];else {sb.append((char)('0' + j));st[j] = true;break;}}return sb.toString();}
}

• Python

class Solution:def getPermutation(self, n: int, k: int) -> str:fact = [1 for _ in range(n)]for i in range(1, n):fact[i] = fact[i - 1] * ires = ""st = [False for _ in range(10)]for i in range(n):for j in range(1, n + 1):if not st[j]:if fact[n - 1 - i] < k:k -= fact[n - 1 - i]else:res += chr(j + ord('0'))st[j] = Truebreakreturn res

时空复杂度分析

• 时间复杂度：$O(n^2)$。计数法中有两重循环。
• 空间复杂度：$O(n)$。