LeetCode–第 k 个排列
<!– more –>
博客阐明
文章所波及的材料来自互联网整顿和集体总结,意在于集体学习和教训汇总,如有什么中央侵权,请分割自己删除,谢谢!
介绍
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"
思路
深度优先搜寻(DFS)+ 剪枝
深度优先搜寻 :能够了解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归,先朝一个方向搜到底,再回溯至上个节点,沿另一个方向搜寻,以此类推。
剪枝 :在搜寻中,遇到 这条路不可能和指标字符串匹配胜利 的状况(例如:此矩阵元素和指标字符不同、此元素已被拜访),则应立即返回,称之为 可行性剪枝。
步骤
如果 kk 大于这一个分支将要产生的叶子结点数,间接跳过这个分支,这个操作叫「剪枝」
如果 kk 小于等于这一个分支将要产生的叶子结点数,那阐明所求的全排列肯定在这一个分支将要产生的叶子结点里,须要递归求解
代码
class Solution {public String getPermutation(int n, int k) {
// 初始化阶乘数组
int[] factorial = new int[n+1];
calculateFactorial(factorial,n);
// 查找全排列的布尔数组
boolean[] temp = new boolean[n+1];
Arrays.fill(temp,false);
// 动静字符串
StringBuilder path = new StringBuilder();
dfs(temp,factorial,0,path,k,n);
return path.toString();}
private void dfs(boolean[] temp,int factorial[],int index,StringBuilder path,int k,int n){if(index == n){return;}
// 全排列个数
int cnt = factorial[n-1-index];
for(int i = 1; i <= n; i++){if(temp[i]){continue;}
// 过后全排列个数
if(cnt < k){
k -= cnt;
continue;
}
path.append(i);
temp[i] = true;
dfs(temp,factorial,index+1,path,k,n);
return;
}
}
// 计算阶乘数组
private void calculateFactorial(int[] factorial, int n){factorial[0] = 1;
for(int i = 1; i <= n; i++){factorial[i] = factorial[i-1]*i;
}
}
}
感激
Leetcode
以及勤奋的本人,集体博客,GitHub