第k个排列

[louzhedong]

习题

出处：LeetCode 算法第60题

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

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

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

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

说明：

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

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

思路

仔细想一下可以找到一下规律：

n个数的的第k个排列为：

a1, a2, a3,...an;

接下来我们一个一个数的选取，如何确定第一个数应该是哪一个呢？选取第一个数后剩下全排列的个数为(n-1)! 所以选取的第一个数应该为第

K1 = k；

a1 = K1/(n-1)!位数字

同理当选完a1后只剩下n-1个数字，在确定第二个数应该选择哪个.

a2 = K2 / (n-2)!

K2 = K1 % (n-1)!

........

a(n-1) = K(n-1) / 1！

K(n-1) = k(n-2) % 2!

an = K(n-1)

解答

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  if (n == 0) {
    return '';
  }
  var fact = [1, 1];
  for (var i = 2; i <= n; i++) {
    fact[i] = i * fact[i - 1];
  }

  var nums = [];
  for (var i = 0; i < n; i++) {
    nums[i] = i + 1;
  }

  for (var i = 0; i < n; i++) {
    var index = Math.floor((k - 1) / fact[n - 1 - i]);
    var swap = nums[i + index];
    for (var j = i + index; j > i; j--) {
      nums[j] = nums[j - 1];
    }
    nums[i] = swap;
    k -= index * fact[n - 1 - i];
  }

  return nums.join('');
};

console.log(getPermutation(3, 3));