Сложность: 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).
Используйте коэффициенты факториалов для построения перестановки.
Верните строку перестановки.
😎 Решение:
class Solution {
public function getPermutation($n, $k) {
$factorials = array_fill(0, $n, 1);
$nums = [];
for ($i = 1; $i < $n; $i++) {
$factorials[$i] = $factorials[$i - 1] * $i;
$nums[] = strval($i + 1);
}
$k--;
$result = "";
for ($i = $n - 1; $i >= 0; $i--) {
$idx = intdiv($k, $factorials[$i]);
$k -= $idx * $factorials[$i];
$result .= $nums[$idx];
array_splice($nums, $idx, 1);
}
return $result;
}
}Ставь 👍 и забирай 📚 Базу знаний