這篇文章主要講解了“C++如何實(shí)現(xiàn)序列排序”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C++如何實(shí)現(xiàn)序列排序”吧！

創(chuàng)新互聯(lián)公司致力于成都網(wǎng)站制作、網(wǎng)站建設(shè),成都網(wǎng)站設(shè)計(jì),集團(tuán)網(wǎng)站建設(shè)等服務(wù)標(biāo)準(zhǔn)化，推過標(biāo)準(zhǔn)化降低中小企業(yè)的建站的成本，并持續(xù)提升建站的定制化服務(wù)水平進(jìn)行質(zhì)量交付，讓企業(yè)網(wǎng)站從市場(chǎng)競(jìng)爭(zhēng)中脫穎而出。 選擇創(chuàng)新互聯(lián)公司，就選擇了安全、穩(wěn)定、美觀的網(wǎng)站建設(shè)服務(wù)！

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:

1. "123"

2. "132"

3. "213"

4. "231"

5. "312"

6. "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個(gè)數(shù)字的第k個(gè)排列組合，由于其特殊性，我們不用將所有的排列組合的情況都求出來，然后返回其第k個(gè)，這里可以只求出第k個(gè)排列組合即可，那么難點(diǎn)就在于如何知道數(shù)字的排列順序，首先要知道當(dāng) n = 3 時(shí)，其排列組合共有 3! = 6 種，當(dāng) n = 4 時(shí)，其排列組合共有 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ā)現(xiàn)，每一位上 1,2,3,4 分別都出現(xiàn)了6次，當(dāng)最高位上的數(shù)字確定了，第二高位每個(gè)數(shù)字都出現(xiàn)了2次，當(dāng)?shù)诙呶灰泊_定了，第三高位上的數(shù)字都只出現(xiàn)了1次，當(dāng)?shù)谌呶淮_定了，那么第四高位上的數(shù)字也只能出現(xiàn)一次，下面來看 k = 17 這種情況的每位數(shù)字如何確定，由于 k = 17 是轉(zhuǎn)化為數(shù)組下標(biāo)為 16：

最高位可取 1,2,3,4 中的一個(gè)，每個(gè)數(shù)字出現(xiàn) 3！= 6 次（因?yàn)楫?dāng)最高位確定了，后面三位可以任意排列，所以是 3！，那么最高位的數(shù)字就會(huì)重復(fù) 3！次），所以 k = 16 的第一位數(shù)字的下標(biāo)為 16 / 6 = 2，在 "1234" 中即3被取出。這里的k是要求的坐標(biāo)為k的全排列序列，定義 k" 為當(dāng)最高位確定后，要求的全排序列在新范圍中的位置，同理，k"" 為當(dāng)?shù)诙邽榇_定后，所要求的全排列序列在新范圍中的位置，以此類推，下面來具體看看：

第二位此時(shí)從 1,2,4 中取一個(gè)，k = 16，則此時(shí)的 k" = 16 % (3!) = 4，注意思考這里為何要取余，如果對(duì)這 24 個(gè)數(shù)以6個(gè)一組來分，那么 k=16 這個(gè)位置就是在第三組（k/6 = 2）中的第五個(gè)（k%6 = 4）數(shù)字。如下所示，而剩下的每個(gè)數(shù)字出現(xiàn) 2！= 2 次，所以第二數(shù)字的下標(biāo)為 4 / 2 = 2，在 "124" 中即4被取出。

3124
3142
3214
3241
3412 <--- k" = 4
3421

第三位此時(shí)從 1,2 中去一個(gè)，k" = 4，則此時(shí)的 k"" = 4 % (2!) = 0，如下所示，而剩下的每個(gè)數(shù)字出現(xiàn) 1！= 1 次，所以第三個(gè)數(shù)字的下標(biāo)為 0 / 1 = 0，在 "12" 中即1被取出。

3412 <--- k"" = 0
3421

第四位是從2中取一個(gè)，k"" = 0，則此時(shí)的 k""" = 0 % (1!) = 0，如下所示，而剩下的每個(gè)數(shù)字出現(xiàn) 0！= 1 次，所以第四個(gè)數(shù)字的下標(biāo)為 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;
    }
};

感謝各位的閱讀，以上就是“C++如何實(shí)現(xiàn)序列排序”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)C++如何實(shí)現(xiàn)序列排序這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

網(wǎng)站名稱：C++如何實(shí)現(xiàn)序列排序
轉(zhuǎn)載來源：http://jinyejixie.com/article34/ipjpse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、動(dòng)態(tài)網(wǎng)站、響應(yīng)式網(wǎng)站、定制開發(fā)、服務(wù)器托管、用戶體驗(yàn)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)