Open
Description
习题
出处：LeetCode 算法第60题
给出集合
[1,2,3,…,*n*]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。
说明：
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3 输出: "213"示例 2:
输入: n = 4, k = 9 输出: "2314"
思路
仔细想一下可以找到一下规律：
n个数的的第k个排列为：
a1, a2, a3,...an;
接下来我们一个一个数的选取，如何确定第一个数应该是哪一个呢？选取第一个数后剩下全排列的个数为(n-1)! 所以选取的第一个数应该为第
K1 = k；
a1 = K1/(n-1)!位数字
同理当选完a1后只剩下n-1个数字，在确定第二个数应该选择哪个.
a2 = K2 / (n-2)!
K2 = K1 % (n-1)!
........
a(n-1) = K(n-1) / 1！
K(n-1) = k(n-2) % 2!
an = K(n-1)
解答
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getPermutation = function (n, k) {
if (n == 0) {
return '';
}
var fact = [1, 1];
for (var i = 2; i <= n; i++) {
fact[i] = i * fact[i - 1];
}
var nums = [];
for (var i = 0; i < n; i++) {
nums[i] = i + 1;
}
for (var i = 0; i < n; i++) {
var index = Math.floor((k - 1) / fact[n - 1 - i]);
var swap = nums[i + index];
for (var j = i + index; j > i; j--) {
nums[j] = nums[j - 1];
}
nums[i] = swap;
k -= index * fact[n - 1 - i];
}
return nums.join('');
};
console.log(getPermutation(3, 3));Metadata
Assignees
Labels
No labels