給出集合 [1,2,3,...,n]吃引，其所有元素共有 n! 種排列。
按大小順序列出所有排列情況，并一一標(biāo)記期升，當(dāng) n = 3 時(shí), 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
給定 n 和 k，返回第 k 個(gè)排列互躬。
示例 1：
輸入：n = 3, k = 3
輸出："213"
示例 2：
輸入：n = 4, k = 9
輸出："2314"
示例 3：
輸入：n = 3, k = 1
輸出："123"
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutation-sequence
解題思路
為了去掉不必要的計(jì)算, 想要直接找到第k個(gè)全排列序列
首先明確: 序列長(zhǎng)度為n時(shí)
比如藥確定第一位數(shù)字, 先假定為1, 那剩下有幾種可能? count = (n-1)!種
如果 k > count, 則說(shuō)明第一位不是 1, 反過(guò)來(lái)如果 k <= count, 則說(shuō)明第一位是 1
以此類(lèi)推, 找出每一位
代碼
class Solution {
int[] factorial;
public String getPermutation(int n, int k) {
StringBuilder path = new StringBuilder();
calculateFactorial(n);
boolean[] used = new boolean[n];
dfs(n, k, used, path);
return path.toString();
}
private void dfs(int n, int k, boolean[] used, StringBuilder path) {
if (path.length() == n) {
return;
}
// count是當(dāng)前想要確定的這一位數(shù)取定時(shí)后續(xù)序列的個(gè)數(shù)
// 也就是 count = (n - 1)!
int count = factorial[n - 1 - path.length()];
for (int i = 0; i < n; i++) {
// 如果當(dāng)前數(shù)已經(jīng)取出, 跳過(guò)
if (used[i]) {
continue;
}
// count < k 則當(dāng)前元素不是該位置應(yīng)該取出的數(shù)
if (count < k) {
// 將k減掉count
k -= count;
continue;
}
// 選定了加追加到結(jié)果
path.append(i + 1);
// 并標(biāo)記為已取出
used[i] = true;
dfs(n, k, used, path);
return;
}
}
/**
* 計(jì)算出n的階乘存到數(shù)組
* 數(shù)組第0個(gè)元素對(duì)應(yīng) 0!, 第1個(gè)元素對(duì)應(yīng) 1!, 以此類(lèi)推
*
* @param n 計(jì)算階乘
* @return void
*/
private void calculateFactorial(int n) {
factorial = new int[n + 1];
factorial[0] = 1; // 0! = 1
for (int i = 1; i <= n; i++) {
factorial[i] = i * factorial[i - 1];
}
}
}
