題目鏈接
tag:
- Medium哲鸳；
question：
??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"
思路：
??這道題是讓求出n個數字的第k個排列組合，由于其特殊性，我們不用將所有的排列組合的情況都求出來弧圆，然后返回其第k個倡勇，我們可以只求出第k個排列組合即可痕貌，那么難點就在于如何知道數字的排列順序括丁，可參見網友喜刷刷的博客凌箕，首先我們要知道當n = 3時，其排列組合共有3! = 6種决侈，當n = 4時螺垢，其排列組合共有4! = 24種，我們就以n = 4, k = 17的情況來分析颜及，所有排列組合情況如下：
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <--- k = 17
3421
4123
4132
4213
4231
4312
4321
我們可以發(fā)現甩苛，每一位上1,2,3,4分別都出現了6次蹂楣，當最高位上的數字確定了俏站，第二高位每個數字都出現了2次，當第二高位也確定了痊土，第三高位上的數字都只出現了1次肄扎，當第三高位確定了，那么第四高位上的數字也只能出現一次赁酝，下面我們來看k = 17這種情況的每位數字如何確定犯祠，由于k = 17是轉化為數組下標為16：
最高位可取1,2,3,4中的一個，每個數字出現3酌呆！= 6次（因為當最高位確定了衡载，后面三位可以任意排列，所以是3隙袁！痰娱，那么最高位的數字就會重復3！次）菩收，所以k = 16的第一位數字的下標為16 / 6 = 2梨睁，在 "1234" 中即3被取出。這里我們的k是要求的坐標為k的全排列序列娜饵，我們定義 k' 為當最高位確定后坡贺，要求的全排序列在新范圍中的位置，同理，k'' 為當第二高為確定后遍坟，所要求的全排列序列在新范圍中的位置拳亿，以此類推，下面來具體看看：
第二位此時從1,2,4中取一個愿伴，k = 16风瘦，則此時的 k' = 16 % (3!) = 4，注意思考這里為何要取余公般，如果對這24個數以6個一組來分万搔，那么k=16這個位置就是在第三組（k/6 = 2）中的第五個（k%6 = 4）數字。如下所示官帘，而剩下的每個數字出現2瞬雹！= 2次，所以第二數字的下標為4 / 2 = 2刽虹，在 "124" 中即4被取出酗捌。
3124
3142
3214
3241
3412 <--- k' = 4
3421
第三位此時從1,2中去一個，k' = 4涌哲，則此時的k'' = 4 % (2!) = 0胖缤，如下所示，而剩下的每個數字出現1阀圾！= 1次哪廓，所以第三個數字的下標為 0 / 1 = 0，在 "12" 中即1被取出初烘。
3412 <--- k'' = 0
3421
第四位是從2中取一個涡真，k'' = 0，則此時的k''' = 0 % (1!) = 0肾筐，如下所示哆料，而剩下的每個數字出現0！= 1次吗铐，所以第四個數字的下標為0 / 1= 0东亦，在 "2" 中即2被取出。
3412 <--- k''' = 0
那么我們就可以找出規(guī)律了
a1 = k / (n - 1)!
k1 = k
a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...
an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!
an = kn-1 / 0!
kn = kn-1 % 0!
代碼如下：
class Solution {
public:
string getPermutation(int n, int k) {
string res;
string num = "123456789";
vector<int> f(n, 1);
for (int i=1; i<n; ++i)
f[i] = f[i-1]*i;
--k;
for (int i=n; i>=1; --i) {
int j = k / f[i-1];
k %= f[i-1];
res.push_back(num[j]);
num.erase(j, 1);
}
return res;
}
};
