Problem
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.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3 Output: "213" Example 2:
Input: n = 4, k = 9 Output: "2314" Solution
/** * @param {number} n * @param {number} k * @return {string} */ var getPermutation = function(n, k) { var str = ''; var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]; var factorial = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]; // n! var tmp1 = 0; var tmp2 = 0; k--; for (var j = n; j >= 1; j--) { tmp1 = factorial[j - 1]; tmp2 = Math.floor(k / tmp1); k %= tmp1; str += nums[tmp2]; nums.splice(tmp2, 1); } return str; }; Explain:
用回溯的方法会超时， 需要用数学规律解的.就是依次找出放在第 index 位的数字。
k-- 这里比较难理解，是用来纠正 k 正好整除于某个阶乘数的特殊情况，即 k % factorial[i] === 0 时。
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).