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 kth permutation sequence.
Example:
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Link:
https://leetcode.com/problems/permutation-sequence/description/
解题方法：
找第k个permutation, 当给定n和k时：
以1开头的permutation有(n - 1)!个，如果k > (n - 1)! 说明一定不是以1开头的，同理2其他数开头的permutation都有(n - 1)!个，所以可以一次类推一位一位得到所要的permutation。
Tips:
本来想用linked list来优化时间复杂度，做完才发现linked list也是O(N^2)的。。。。
Time Complexity：
O(N^2)
完整代码：
public:
int val;
node(int i) {val = i; next = NULL;}
node* next;
};
string getPermutation(int n, int k) {
int total = 1;
node* root = new node(0);
node* move = root;
for(int i = 1; i <= n; i++) {
total *= i;
move->next = new node(i);
move = move->next;
}
total /= n;
string result;
move = root;
int f = n - 1;
for(int i = 1; i <= n && k > 0; i++) {
cout<<result<<endl;
while(total < k) {
move = move->next;
k -= total;
}
result += to_string(move->next->val);
move->next = move->next->next;
if(f > 1)
total /= f--;
move = root;
}
return result;
}
