文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 回溯
    • 2.2 數(shù)學(xué)-康托展開

1. 題目

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

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

“123”
“132”
“213”
“231”
“312”
“321”

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

說(shuō)明： 給定 n 的范圍是 [1, 9]。 給定 k 的范圍是[1, n!]。示例 1: 輸入: n = 3, k = 3 輸出: "213"示例 2: 輸入: n = 4, k = 9 輸出: "2314"

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutation-sequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 回溯

class Solution { public:string getPermutation(int n, int k) {string ans, temp;bool visited[10] = {0};int count = 0;permute(n, k, count, 0, temp, ans, visited);return ans;}void permute(int &n, int &k, int& count, int bit, string &temp, string &ans, bool* visited){if(count > k)return;if(bit == n){count++;if(count == k)ans = temp;}for(int i = 1; i <= n; i++){if(visited[i])// i寫入了答案，繼續(xù)下一個(gè)數(shù)continue;temp.push_back(i+'0');visited[i]=true;permute(n, k, count, bit+1, temp, ans, visited);temp.pop_back();visited[i]=false;}} };

2.2 數(shù)學(xué)-康托展開

class Solution { public:string getPermutation(int n, int k) {int factor[10] = {1,1,2,6,24,120,720,5040,40320,362880};//階乘數(shù)string num = "123456789";string ans;int bit;while(n > 0){bit = (k-1)/factor[n-1];//確定第一位數(shù)的時(shí)候，后面有f[n-1]種排列ans.push_back(num[bit]);num.erase(num.begin()+bit);//該位數(shù)寫入答案了，刪除k -= bit*factor[n-1];n--;}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 60. 第k个排列（回溯 康托展开）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。