給出集合?[1,2,3,...,n]，其所有元素共有?n!?種排列。

按大小順序列出所有排列情況，并一一標(biāo)記，當(dāng)?n = 3?時(shí), 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

給定?n?和?k，返回第?k?個(gè)排列。

示例 1：

輸入：n = 3, k = 3
輸出："213"

示例 2：

輸入：n = 4, k = 9
輸出："2314"

示例 3：

輸入：n = 3, k = 1
輸出："123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

解題思路：

例如： n = 4， k = 9

????????可以知道全排列有：4*3*2*1 = 24種，如下：紅色框住的為第9個(gè)

? ? ? ? ? ? ? ??

????????從上圖可知，以1開(kāi)頭的全排列 (4-1)! = 6 共6種 ；

? ? ? ? 9 /?6 = 1······3，也就是該數(shù)位于2開(kāi)頭的第三個(gè)。

? ? ? ? 同理，第一位2確定后，剩下三位 1 3 4，接下來(lái)需要確定第二位；

? ? ? ?

? ? ? ? ? ? ??

? ? ? ? 由上面的圖片可知， 1 3 4全排列每一列分別有兩個(gè)數(shù)（3-1）！，3 / 2 = 1······1，可知位于第二列開(kāi)頭的第一個(gè)

然后確定第三位 ，第三位則還剩下2個(gè)數(shù)：1和4；

? ? ? ? 1和4的全排列：

? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? 1 4排列，每類(lèi)（2-1)! = 1，1 / 1 = 1·····0,可知位于1開(kāi)頭的第一個(gè)

? ? ? ? 最后一位數(shù)，只有一種情況:? （1-1)！ = 1

具體算法如下：

1、定義一個(gè)逆康托數(shù)組，記錄n位數(shù)字對(duì)應(yīng)每個(gè)數(shù)字開(kāi)頭序列的個(gè)數(shù)，例如4位數(shù)prenum[1, 1, 2, 6]

將k值-1，再進(jìn)行計(jì)算，這里-1是為了? 9 % 6 = 3，而數(shù)組下標(biāo)從0開(kāi)始，-1后方便計(jì)算。

2、定義一個(gè)valid數(shù)組[0.....n];記錄還沒(méi)有被使用的數(shù)字， 已經(jīng)使用的需要移除

3、(k -1 ) / prenum[n - i - 1]? ?+ 1就是分別計(jì)算每一位數(shù)字位于那一列；例如 （9 -1）/ 6? + 1= 2，說(shuō)明第一個(gè)數(shù)字為2，ans累加vali[2] ,2被使用后erase掉，valid中剩余[0,1,3,4]

? ? ? ? 然后k記錄剩余未計(jì)算的數(shù) 8 % 6 = 2

? ? ? ? k = 2再重復(fù)計(jì)算，可得到 2/2 + 1 = 2;? 再取走valid中的第2個(gè)

? ? ? ? 同理依次取完。

完整代碼如下：

class Solution {
public:string getPermutation(int n, int k) {//prenum = {0!, 1!, 2!, 3!, .....(n-1)!}vector<int> pernum(n);pernum[0] = 1;for(int i= 1; i < n; i++) {pernum[i] = pernum[i-1] * i;}//k-- 方便取余后計(jì)算k--;string ans;vector<int> valid(n+1);//生成[0,1,2....n]的數(shù)組iota(valid.begin(), valid.end(), 0);for(int i = 0; i < n; i++) {int order = k / pernum[n-i-1] + 1;ans += (valid[order] + '0');//用了就從數(shù)組中刪除valid.erase(valid.begin() + order);k %= pernum[n-i-1];}return ans;}
};

拓展：康托展開(kāi)，也就是在全排列中，給定一個(gè)序列，求該序列位于第幾個(gè)。

#include <iostream>
#include <string>
using namespace std;class Solution {public://求階乘int fact(int x) {int ret = 1;for(int i = 2; i <= x; i++) {ret *= i;}return ret;}int getStringId(string str) {int len = str.size();int ans = 0;for(int i = 0; i < len; i++) {int cnt = 0;//記錄后面的數(shù)有幾個(gè)比當(dāng)前的數(shù)小；//例如2314  314中只有1個(gè)數(shù)比第一位小，說(shuō)明該數(shù)位于第二列。for(int j = i + 1 ; j < len; j++) {if(str[j] < str[i]) {cnt ++;}}ans += cnt*fact(len- i -1);}return ans+1;}
};
int main()
{string s;cin >> s;Solution sol;cout << "位于序列第：" << sol.getStringId(s) << " 位" << endl;return 0;
}