60. Permutation Sequence

[Tcdian]

60. Permutation Sequence

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

Note

• 给定 n 的范围是 [1, 9]。
• 给定 k 的范围是[1, n!]。

Example 1

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

Example 2

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

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function(n, k) {
    const counts = new Array(n);
    const digits = new Array(n);
    for (let i = 0; i < n; i++) {
        digits[i] = i + 1;
        counts[i] = (counts[i - 1] || 1) * digits[i];
    }
    let result = '';
    for (let i = 1; i <= n; i++) {
        const digitIndex = Math.ceil(k / counts[n - i - 1]) - 1;
        k %= counts[n - i - 1];
        result += digits.splice(digitIndex, 1);
    }
    return result;
};

• TypeScript Solution

function getPermutation(n: number, k: number): string {
    const counts: number[] = new Array(n);
    const digits: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
        digits[i] = i + 1;
        counts[i] = (counts[i - 1] || 1) * digits[i];
    }
    let result = '';
    for (let i = 1; i <= n; i++) {
        const digitIndex = Math.ceil(k / counts[n - i - 1]) - 1;
        k %= counts[n - i - 1];
        result += digits.splice(digitIndex, 1);
    }
    return result;
};