题目
排列序列
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123" "132" "213" "231" "312" "321"
给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3 输出："213"
示例 2：
输入：n = 4, k = 9 输出："2314"
示例 3：
输入：n = 3, k = 1 输出："123"
提示：
1 <= n <= 9 1 <= k <= n!
题解
解题分析
解题思路
- 根据题意可知，对于 n 个不同的元素（例如数 1, 2, ⋯, n），它们可以组成的排列总数目为 n^2。
- 其实我们就是求 n-1 个元素组成的排列中，排列中第 k 个值。
- 然后我们对值进行枚举，然后最后得到结果。（备注，具体的逻辑可以看看代码注释）
复杂度
- 时间复杂度 O(N^2)
- 空间复杂度 O(N)
解题代码
题解代码如下（代码中有详细的注释说明）：
class Solution { public String getPermutation(int n, int k) { // n 阶乘 映射集 0...n-1 int[] factorial = new int[n]; factorial[0] = 1; for (int i = 1; i < n; ++i) { factorial[i] = factorial[i - 1] * i; } // k 需要先自减一 原因： // 不妨设分子为 k，那么得到的公式可能是这样的： // ai = ⌊k / (n-1)!⌋ + 1 // 尝试使用以上公式计算 a1: // （1）当 k < (n-1)! 时，a1 = ⌊k / (n-1)!⌋ + 1 = 1，正确 // （2）当 k = (n-1)! 时，a1 = ⌊k / (n-1)!⌋ + 1 = 2，错误 // 而使用 ai = ⌊(k-1) / (n-1)!⌋ + 1 却能正确处理这种情况 // 即：只是简洁了数学公式的使用，如果不自减一的话，需要应对多种情况 --k; // 结果 StringBuffer ans = new StringBuffer(); // 所有的值为 1 int[] valid = new int[n + 1]; // 填充默认值 Arrays.fill(valid, 1); // 排列中 依次取得的排列的数的个数 1个...n个 for (int i = 1; i <= n; ++i) { // 此公式可算出上面的数对应的从 1...n 中哪个数 order | n - i 为了对应 factorial 下标,获取剩余个数排列种类总数 int order = k / factorial[n - i] + 1; // 依次寻找对应的数 从 1...n for (int j = 1; j <= n; ++j) { // 找到一个数，若没有进入过结果排列集，减一，直至 order == 0 则表示找到该排列中的第 i 个数，修改标志集对应位置为已进入结果排序集 order -= valid[j]; if (order == 0) { ans.append(j); valid[j] = 0; break; } } // 之后 k 对于已取得的数的排列位数取余，得到下一位需要的 k %= factorial[n - i]; } return ans.toString(); } }
提交后反馈结果如下：
网络异常，图片无法展示
|
