一天一大 lee(第k个排列)难度:中等-Day20200905

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

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

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  let _result = '',
      nums = [], // 存放待排列元素
      factorial = 1; 
  for (let i = 1; i <= n; i++) {
    nums.push(i); 
    factorial = factorial * i;
  }
  // 计数和索引差1
  k= k-1;

  while (nums.length > 0) {
    factorial = factorial / nums.length; // 确定一个元素后，待排列的组合种类减少为（n-x）的阶乘
    let index = parseInt(k / factorial,10);     // 当前选择的数字的索引
    _result += nums[index];               // 加上当前选的数字
    nums.splice(index, 1);               // nums删去选的这个数字
    k = k % factorial;                   // 更新 k，
  }
  return _result;
}

var getPermutation = function (n, k) {
  let used = new Map(),
    factorial = 1;
  for (let i = 1; i <= n; i++) {
    factorial = factorial * i;
  }

  function helper(temp) {

    let len = temp.length;

    if (len == n) return temp.join('');

    factorial = factorial / (n - len); // 待排列的元素存在的组合数

    for (let i = 1; i <= n; i++) {
      if (used.has(i)) continue; // 递归时忽略已经排列的元素

      if (k > factorial) { // 如果k大于剩余的组合数，则说明如果此位置排列i则排列完成不能有k种组合
        k = k - factorial; 
        continue; 
      }
      temp.push(i);        // 满足此位置选择i包含大于等于k中组合
      used.set(i, true);
      return helper(temp); // 继续选择i后面的元素
    }
  };

  return helper([]);
}