视频在线一区二区,日韩免费视频,九九福利

[LeetCode] 60. 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"

這道題是讓求出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

可以發現，每一位上 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

那么就可以找出規律了
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;

									    }

									};