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個(gè)permutation, 當(dāng)給定n和k時(shí)：
以1開(kāi)頭的permutation有(n - 1)!個(gè)走搁，如果k > (n - 1)! 說(shuō)明一定不是以1開(kāi)頭的讶隐，同理2其他數(shù)開(kāi)頭的permutation都有(n - 1)!個(gè)楷拳，所以可以一次類(lèi)推一位一位得到所要的permutation。
Tips:
本來(lái)想用linked list來(lái)優(yōu)化時(shí)間復(fù)雜度猪贪，做完才發(fā)現(xiàn)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;
}
