60. 第k個排列
給出集合 [1,2,3,…,n],其所有元素共有 n! 種排列。
按大小順序列出所有排列情況,并一一标記,當 n = 3 時, 所有排列如下:
“123”
“132”
“213”
“231”
“312”
“321”
給定 n 和 k,傳回第 k 個排列。
說明:
給定 n 的範圍是 [1, 9]。
給定 k 的範圍是[1, n!]。
示例 1:
輸入: n = 3, k = 3
輸出: “213”
示例 2:
輸入: n = 4, k = 9
輸出: “2314”
PS:
直接用回溯法做的話需要在回溯到第k個排列時終止就不會逾時了, 但是效率依舊感人
可以用數學的方法來解, 因為數字都是從1開始的連續自然數, 排列出現的次序可以推
算出來, 對于n=4, k=15 找到k=15排列的過程:
1 + 對2,3,4的全排列 (3!個)
2 + 對1,3,4的全排列 (3!個) 3, 1 + 對2,4的全排列(2!個)
3 + 對1,2,4的全排列 (3!個)-------> 3, 2 + 對1,4的全排列(2!個)-------> 3, 2, 1 + 對4的全排列(1!個)-------> 3214
4 + 對1,2,3的全排列 (3!個) 3, 4 + 對1,2的全排列(2!個) 3, 2, 4 + 對1的全排列(1!個)
确定第一位:
k = 14(從0開始計數)
index = k / (n-1)! = 2, 說明第15個數的第一位是3
更新k
k = k - index*(n-1)! = 2
确定第二位:
k = 2
index = k / (n-2)! = 1, 說明第15個數的第二位是2
更新k
k = k - index*(n-2)! = 0
确定第三位:
k = 0
index = k / (n-3)! = 0, 說明第15個數的第三位是1
更新k
k = k - index*(n-3)! = 0
确定第四位:
k = 0
index = k / (n-4)! = 0, 說明第15個數的第四位是4
最終确定n=4時第15個數為3214
class Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
// 候選數字
List<Integer> candidates = new ArrayList<>();
// 分母的階乘數
int[] factorials = new int[n+1];
factorials[0] = 1;
int fact = 1;
for(int i = 1; i <= n; ++i) {
candidates.add(i);
fact *= i;
factorials[i] = fact;
}
k -= 1;
for(int i = n-1; i >= 0; --i) {
// 計算候選數字的index
int index = k / factorials[i];
sb.append(candidates.remove(index));
k -= index*factorials[i];
}
return sb.toString();
}
}