60. Permutation Sequence

Level - hard

Task

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

• "123"
• "132"
• "213"
• "231"
• "312"
• "321"

Given n and k, return the kth permutation sequence.

Объяснение

Это задача на нахождение k-й последовательности перестановки из n чисел.

Перестановка - это упорядоченная выборка из множества.
Например, для n = 3 (1, 2, 3), всевозможные перестановки: "123", "132", "213", "231", "312", "321".

Задача состоит в том, чтобы найти k-ю перестановку в лексикографическом порядке. Лексикографический порядок - это общепринятый алфавитный порядок, используемый для упорядочения слов в словарях.

Например, для n = 3 и k = 3, ответ будет "213".

Чтобы решить эту задачу, можно использовать следующий алгоритм:

1. Сначала вычислить факториалы чисел от 0 до n. Это можно сделать заранее, так как факториалы не изменяются для одного и того же n.
2. Затем создать список чисел от 1 до n, который будет использоваться для формирования перестановок.
3. Инициализировать пустую строку, которая будет содержать k-ю перестановку.
4. Вычислить индекс первого символа k-й перестановки, используя факториалы и деление k на соответствующий факториал.
5. Добавить в строку найденный символ из списка чисел и удалить его из списка.
6. Обновить k, уменьшив его на найденный индекс, умноженный на соответствующий факториал.
7. Повторять шаги 4-6, пока не будет получена k-я перестановка.
8. Вернуть полученную строку как k-ю перестановку.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Example 3:

Input: n = 3, k = 1
Output: "123"

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!