目录
- 排序序列
- 题目
- 示例 1
- 示例 2
- 示例 3
- 提示
- 解答
- 解题思路
- 完整代码
排序序列
题目
给出集合 [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!。对于给定的n和k,我们不妨从左往右确定第k个排列中的每一个位置.上的元素到底是什么。我们首先确定排列中的首个元素a1。根据上述的结论,我们可以知道:以1为a1的排列一共有(n- 1)!个;以2为a1的排列一共有(n- 1)!个;以n为a1的排列一共有(n- 1)!由于我们需要求出从小到大的第k: 个排列,因此:如果k:< (n- 1)! ,我们就可以确定排列的首个元素为1 ;如果(n- 1)!< k:≤2.(n- 1)!,我们就可以确定排列的首个元素为2 ;如果(n- 1).(n- 1)! < k≤n.(n一我们就可以确定排列的首个元素为n。因此,第k个排列的首个元素就是:k- 1a1 =(n- 1)!-+1其中x」表示将X向下取整。当我们确定了a1 后,如何使用相似的思路,确定下一个元素a2呢?实际上,我们考虑以a1为首个元素的所有排列:
以[1,n]\a1 最小的元素为a2的排列一共有(n- 2)!个;以[1,n]\a1 次小的元素为a2的排列一共有(n-2)!个;以[1,n]\a1最大的元素为 a2的排列一共有(n-2)!个;其中[1,n]\a1表示包含1,2,…n中除去a1以外元素的集合。这些排列从编号(a1- 1).(n-1)!开始,到a1.(n- 1)!结束,总计(n-1)!个,因此第k个排列实际.上就对应着这其中的第k:’=(k-1) mod(n- 1)!+1个排列。这样一来,我们就把原问题转化成了一个完全相同但规模减少1的子问题:求[1,n]\a1这n-1个元素组成的排列中,第k’小的排列。算法设第k; 个排列为A1,A2, … . ,An,我们从左往右地确定每一个元素ai。我们用数组valid记录每一个元素是否被使用过。我们从小到大枚举i :我们已经使用过了i- 1个元素,剩余n- i+ 1个元素未使用过,每一个元素作为a;都对应着(n- i)! 个排列,总计(n-i+ 1)! 个排列; .因此在第k个排列中,a;即为剩余未使用过的元素中第k- 1+1小的元(n- i)!素;在确定了a;后,这n-i+1个元素的第k个排列,就等于a;之后跟着剩余n-i个元素的第(k:- 1) mod(n-i)!+1个排列。在实际的代码中,我们可以首先将k; 的值减少1,这样可以减少运算,降低代码出错的概率。对应上述的后两步,即为:因此在第k: 个排列中,A;即为剩余未使用k过的元素中第((n-i)!-+1小的元素;在确定了a;后,这n-i+1个元素的第. k个排列,就等于a;之后跟着剩余n-i个元素的第k mod(n- i)!个排列。实际上,这相当于我们将所有的排列从0开始进行编号。
完整代码
class Solution {public String getPermutation(int n, int k) {int[] factorial = new int[n]; factorial[0] = 1; for (int i = 1; i < n; ++i) { factorial[i] = factorial[i - 1] * i; } --k; StringBuffer ans = new StringBuffer(); int[] valid = new int[n + 1]; Arrays.fill(valid, 1); for (int i = 1; i <= n; ++i) { int order = k / factorial[n - i] + 1; for (int j = 1; j <= n; ++j) { order -= valid[j]; if (order == 0) { ans.append(j); valid[j] = 0; break; } } k %= factorial[n - i]; } return ans.toString(); }
}