60. Permutation Sequence
难度:Medium
刷题内容
原题连接
- https://leetcode.com/problems/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.
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"
˼·1 **- ʱ¼ä¸´ÔÓ¶È: O(n^2)*- ¿Õ¼ä¸´ÔÓ¶È: O(n)***
ÏȽ«ËùÓÐÊý°´Ë³Ðò´æÔÚÓиö×Ö·û´®ÖУ¬È»ºóÑ»·n´Î£¬Ã¿´ÎÕÒµ½ÕýÈ·µÄÊý£¬ÓÉÓÚearseʱ¼ä¸´ÔÓ¶ÈΪn£¬ËùÒÔ×ܵÄʱ¼ä¸´ÔÓ¶ÈΪn^2
class Solution {
public:
string getPermutation(int n, int k){
int arr[n + 1];
string ans,org;
for(int i = 1;i <= n;++i)
{
org.push_back(i + '0');
i == 1 ? arr[i] = 1 : arr[i] = arr[i - 1] * i;
}
for(int i = n - 1;i > 0;--i)
{
int t = k / arr[i];
cout<< t<< endl;
k = (k) % arr[i];
if(!k)
{
k = arr[i];
t--;
}
ans.push_back(org[t]);
org.erase(org.begin() + t);
arr[i] = 0;
}
ans.push_back(org[0]);
return ans;
}
};
