Сложность: hard
Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.
Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.
Пример:
Input: n = 3, k = 3
Output: "213"
👨💻 Алгоритм:
1️⃣Сгенерируйте входной массив nums чисел от 1 до N.
2️⃣Вычислите все факториальные основы от 0 до (N−1)!.
3️⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1).
😎 Решение:
var getPermutation = function (n, k) {
let factorials = new Array(n);
let nums = ["1"];
factorials[0] = 1;
for (let i = 1; i < n; ++i) {
factorials[i] = factorials[i - 1] * i;
nums.push((i + 1).toString());
}
--k;
let output = "";
for (let i = n - 1; i > -1; --i) {
let idx = Math.floor(k / factorials[i]);
k -= idx * factorials[i];
output += nums[idx];
nums.splice(idx, 1);
}
return output;
};Ставь 👍 и забирай 📚 Базу знаний