Without further ado, let’s look at the efficiency of my algorithm:The title description is as follows:

Give the set [1.2.3,... ,n], all of its elements have n! Kind of arrangement. List all permutations in order of size and mark one by one, when n =3, all permutations are as follows:"123"
"132"
"213"
"231"
"312"
"321"Given n and k, return the KTH permutation. Example: Enter n =3, k = 4Output:"231"
Copy the code

Let’s take this picture as an example:The idea is to backtrack. In this example we will start at the first level and work backwards. We will first use a variable num_before to record the number of permutations in front of the current position. The maximum order he can reach starting with 1 is :num_before+(n-floor)! = 0 + (3-1)! 2<k=4, num_before =2, num_before+(n-floor) =2, num_before+(n-floor)! = 2 + (3-1)! =4, which just happens to include k=4, so the first layer goes to 2 and stops there, and then goes down (1, 3 below 2). Let’s look at 1, the largest order that can be reached for a sequence starting with 21 is num_before+(n-floor)! = 2 + (3-2)! =3, less than k=4, so we discard 1 and update num_before to 3, then look at 3, the largest order that can be reached starting with 23 is num_before+(n-floor)! = 3 + (3-2)! =4, including k=4, so we are done with this layer of traversal, move on to the next layer (that is, 1 below 23), we look at 1, his num_before+(n-floor)! = 3 + (3-2)! So theta is equal to 4, that includes k is equal to 4, so we’re done with this layer, and then we go to the next layer, and then we go to the next layer and it’s 4>n is equal to 3, and then our program is done, so we end up with 231 at n is equal to 3 and k is equal to 4. The implementation code is as follows:

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
     * @paramFact fact[I] records whether the number I is already in *@paramThe stringBuilder is used to record the added number *@paramNum_before indicates how many permutations * precede the current position@paramFloor indicates the current number of layers */
    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)<k){
                        num_before+=getN(n-floor);
                    }else{
                        stringBuilder.append(i);
                        fact[i]=1;
                        getK(n,k,fact,stringBuilder,num_before,floor+1);
                    }
                }
            }
        }
    }

    int getN(int n){
        if(n==1||n==0) {return 1;
        }else{
            return n*getN(n-1); }}}Copy the code