Сложность: 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 {
func getPermutation(_ n: Int, _ k: Int) -> String {
var factorials = [Int](repeating: 1, count: n)
var nums = [Character]()
for i in 1..<n {
factorials[i] = factorials[i - 1] * i
nums.append(Character(String(i + 1)))
}
var k = k - 1
var result = ""
for i in stride(from: n - 1, through: 0, by: -1) {
let idx = k / factorials[i]
k -= idx * factorials[i]
result.append(nums[idx])
nums.remove(at: idx)
}
return result
}
}Ставь 👍 и забирай 📚 Базу знаний