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).