本文共 1603 字，大约阅读时间需要 5 分钟。

LeedCode第60题——第K个排列

话不多说先看一下我的算法效率:

题目描述如下:

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下："123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。示例:输入: n = 3, k = 4输出: "231"

下面我们以这张图为例来讲解:

我们的思路是采用回溯的方法，在上面这个例子里面我们会先从第一层往后面遍历(也即1,2,3的顺序)，我们首先使用一个变量num_before来记录当前位置前面的排列数，那么在看1的时候，他前面是没有排列的，num_beore=0，而以1开头的他最多可以达到的排列次序是:num_before+(n-floor)!=0+(3-1)!=2,也就是他最后的那个排列是132，由于2<k=4，我们抛弃1，来看2，此时的num_before应该更新为2,那么以2为开头的排列最大可以达到的次序是num_before+(n-floor)!=2+(3-1)!=4,刚好把k=4包括在内，因此第一层就遍历到2这里就停止了，接着往下面遍历(也就是2下面的1，3)，我们看1，以21为开头的排列可以达到的最大次序是num_before+(n-floor)!=2+(3-2)!=3，小于k=4，因此我们抛弃1，并将num_before更新为3，接着看3，以23开头的可以达到的最大的次序是num_before+(n-floor)!=3+(3-2)!=4，把k=4包括在内了，于是我们这一层的遍历就结束了，接着看下一层(即23下面的1),我们看1，他的num_before+(n-floor)!=3+(3-2)!=4，把k=4包括在内了，于是这一层的遍历也结束了，我们接着来看下一层，而此时看下一层层数是4>n=3,这个时候我们的程序就结束了，于是我们最后在n=3,k=4时得到的结果就是231.实现代码如下：

public class Solution {
       public String getPermutation(int n, int k) {
           StringBuilder stringBuilder = new StringBuilder();        int[] fact = new int[n+1];        getK(n,k,fact,stringBuilder,0,1);        return stringBuilder.toString();    }    /**     * @param n      * @param k     * @param fact fact[i]记录数字i是否已用     * @param stringBuilder 用来记录添加的数字     * @param num_before 表示当前所在位置前面已有多少个排列     * @param floor 表示当前所在的层数     */    public void getK(int n,int k,int[] fact,StringBuilder stringBuilder,int num_before,int floor){
           if(floor==n+1){
               return;        }else{
               int num=0;            for(int i=1;i<=n;i++){
                   if(fact[i]==0){
                       if(num_before+getN(n-floor)

转载地址：http://bolzi.baihongyu.com/