原题地址：第k个排列
给出集合 [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-1)!$个排列的第一位都是1，第二组$(n-1)!$个排列的第一位都是2，所以通过 $k \div (n-1)!$ 直接确定第一位的数字。剩下的位数也可以用同样的方法确定，只需要排除掉前面已经出现过的数字即可。
具体的计算代码实现如下：
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
const getPermutation2 = function(n, k) {
// 计算n-1的总排列数量
let count = 1;
for (let i = 2; i < n; i ++) {
count *= i;
}
// 用来保存某一个数是否已被用过
let flags = new Array(n).fill(false);
// 用来保存结果
let result = '';
// 因为我们计算索引时都是从0开始算的，而题目给的k是从1开始计算的，所以要先减1
k --;
// 依次计算每一位的结果
for (let i = 0; i < n; i ++) {
// 计算当前位要填哪个数字
let index = Math.floor(k / count);
for (let j = 0; j <= index; j ++) {
if (flags[j]) {
index ++;
}
}
// 标记这个数已经被用过了
flags[index] = true;
// 将这个数加入到结果中去，注意要加1
result += `${index + 1}`;
// 计算在剩下位数的排列中是第几个
k = k % count;
// 计算剩下位数的排列个数
count /= (n - i - 1);
}
return result;
};
测试：
let start = new Date();
const test = getPermutation2;
console.log(test(1,1)); // 1
console.log(test(2,2)); // 21
console.log(test(3,2)); // 132
console.log(test(4,9)); // 2314
console.log(new Date().getTime() - start.getTime()); // 7
时间复杂度： 总共有$N$位要计算，计算每一位时最多需要$N$次判断，所以时间复杂度为$O(N^2)$
空间复杂度： 需要一个额外的数组来保存每一个数字是否被用过，空间复杂复杂度为$O(N)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 17,2019