60. Permutation Sequence
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| class Solution { int factorial(int n) { return n == 1 ? 1 : n * factorial(n-1); } string helper(int n, int k) { if(n == 1) return string(1, '0' + k); int comb = factorial(n-1);
int front = (k - 1) / comb; return string(1, '1' + front) + helper(n-1,k - front * comb); } public: string getPermutation(int n, int k) { string res = helper(n,k); for(int num = 1; num <= n; num++) { for(int i = 0; i < res.length(); i++) { if((res[i] & 0b1111) == num) { for(int j = i + 1; j < res.length(); j++) if(res[j] >= res[i]) res[j]++; break; } } } return res; } };
|