LeetCode如何解决第k个排列问题

小编给大家分享一下LeetCode如何解决第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如何解决第k个排列问题"这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！