Leetcode60. permutation sequence

Title transmission address :https://leetcode.cn/problems/permutation-sequence/
Let's first show you a recursive solution using full permutation , But it does not meet the performance requirements of the topic .
Code ：

  public static String getPermutation(int n, int k) {
    
        String[] allArrange = getAllArrange(n);
        Arrays.sort(allArrange);
        return allArrange[k - 1];
    }

    /** *  Full Permutation  * * @param n * @return */
    public static String[] getAllArrange(int n) {
    
        if (n == 1) {
    
            String[] res = new String[1];
            res[0] = "1";
            return res;
        }
        List<String> list = new ArrayList<>();
        String[] allArrange = getAllArrange(n - 1);
        for (int i = 0; i < allArrange.length; i++) {
    
            String str = allArrange[i];
            for (int j = 0; j <= str.length(); j++) {
    
                StringBuilder stringBuilder = new StringBuilder(str);
                stringBuilder.insert(j, n);
                list.add(stringBuilder.toString());
            }
        }
        String[] res;
        res = list.toArray(new String[0]);
        return res;
    }

The really powerful code is as follows

  public static String getPermutation(int n, int k) {
    
        StringBuilder stringBuilder = new StringBuilder();
        while (n > 0) {
    
            stringBuilder.insert(0, n);
            n--;
        }
        // such as n=4, be result=1234
        return getResult(stringBuilder.toString(), k);
    }

    public static String getResult(String str, int k) {
    
        // Dealing with border situations 
        if (str.length() == 1) {
    
            return str;
        }
        int index = 0;
        int factorial = doFactorial(str.length() - 1);
        // Calculate the first character  // such as n=4,k=9 Under the circumstances , The correct answer to this question should be "2314", factorial=6,
        //  and 9/6=1, Go through the following while After the cycle ,fisrtChar=2, k=3
        while (k > factorial) {
    
            index++;
            k -= factorial;
        }
        if (k == 0 && index == 0) {
    
            return str;
        }
        char firstChar = str.charAt(index);
        String res = new StringBuilder(str).deleteCharAt(index).toString();
        String result = getResult(res, k);
        StringBuilder stringBuilder = new StringBuilder(result);
        stringBuilder.insert(0, firstChar);
        return stringBuilder.toString();
    }

    /** *  Factorial  * @param m * @return */
    public static int doFactorial(int m) {
    
        if (m == 1) {
    
            return 1;
        }
        return doFactorial(m - 1) * m;
    }

Operational efficiency ：