60. Permutation Sequence
1. Description
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 $k^{th}$ permutation sequence.
2. Example
Example 1:
Input: n = 3, k = 3
Output: “213”
Example 2:
Input: n = 4, k = 9
Output: “2314”
Example 3:
Input: n = 3, k = 1
Output: “123”
3. Constraints
- 1 <= n <= 9
- 1 <= k <= n!
4. Solutions
My Accepted Solution
I don’t know how to calculate its complexity😅
Time complexity: O()
Space complexity: O()
// the permutaion likes a number, every digit has a right
// for example, 123, the digit '1' has the right of 100, and only its later digit moves 10 times, it move one time
// also, the permution "123", the letter '1' also has the right of 2!
// only its later string being totally reversed ordered, it will move one time, to the next letter '2'
// so, we could use this methord to dertermine the current letter, and get the result using recursion process
// And this process has a name: Cantor expansion
class Solution
{
private:
int getFactorial(int number)
{
int result = 1;
for(int i = 1; i <= number; i++)
result *= i;
return result;
}
public:
// string getPermutation(int n, int k)
string getPermutation(int n, int k)
{
string result("123456789");
result = result.substr(0, n);
for(int i = 0; i < n; i++)
{
sort(result.begin() + i, result.end());
int index = 0;
for(int base = getFactorial(n - i - 1); k > base; index++)
k -= base;
swap(result[i], result[i + index]);
}
return result;
}
};