LeetCode–第k个排列

归子莫

发布于：2020年9月5日

LeetCode–第k个排列

博客说明

文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！

介绍

60. 第k个排列

题目

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

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k，返回第 k 个排列。

说明：

1 2	给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。

示例 1:

1 2	输入: n = 3, k = 3 输出: "213"

示例 2:

1 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;
        }
    }
}