60.Permutation sequence

• First, Let's see the description of the 60th question in leetcode:

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123" "132" "213" "231" "312" "321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

• Second,Let's analyze the problem:
  we can set a example: if n=4, k=10, without computer how can I get the result?
  1, In this situation, we know that all the possibilities are 1*** 2*** 3*** 4*** (means a number ), the total amount is 43! =24.
  2, Also we can see 1 *** has 3! =6 possibilities. Because 10/6 =1,10%6=4, so the first number must be 2 which is the second smallest number.
  3, Now left numbers are, 1,3,4, the problem becomes that if n=3,k=4 how can I get the result?
  4, Just repeat these steps. We finally get the
  1,2,3,4: n=4,k=10: 3!=6, 10/6=1...4; So the first number is 2;
  1, 3, 4: n=3,k=4 : 2!=2, 4/2 =1...2(rather than 2...0); So the second number is 3;
  1, 4: n=2,k=2: 1!=1, 2/1=1...1(rather than 2...0);So the third number is 4;
  So the result is "2341" when n=4 and k=10.
• Third, what should we be attention to?

1. When (n-1)! is divisible by k, for example 4/1, its result is 3...1
2. Attention: 0!=1
3. Because we get the number's index, we must remove it. For example, when we know the first number is 2 which is the second smallest in 1.2.3.4. Then left number is 1,3,4.
4. In order to realize tips 3, we need a particular data struct. Here I use list, but sorting it spends too much time.Maybe we can change to priority
   queue or heap or trees.
5. If you wanna improve the spend, you need to realize the calculation of n! dynamically.

• Fourth, here is my code(it's not the best solution, just a method, we can optimize if possible)

import java.rmi.server.RemoteStub;
import java.util.*;
//in order to improve the running time, you can change the way to calculate n!, then sort in another way
public class Solution {
           
    public String getPermutation(int n, int k) {
        if(k<1||k>calculateNthFactorial(n)) return "error";
        StringBuilder s=new StringBuilder();
        int kth=k;
        int rest=n;
        int[] result=new int[n];
        for(int i=0;rest>0 && i<n;i++,rest--){
            int temp=calculateNthFactorial(rest-1);
            if(kth % temp==0){
                result[i]=kth/temp-1;
                kth=temp;               
            }
            else{
                result[i]=kth/temp;
                kth=kth%temp;
        
            }           
        }
        //Initialize the list
        List<Integer> help = new ArrayList<Integer>();
        for(int i=1;i<=n;i++) help.add(i);
        for(int e:result){
            Collections.sort(help, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    // TODO Auto-generated method stub
                    if(o1>o2) return 1;
                    else if(o1<o2) return -1;
                    return 0;
                }
            });     
            //System.out.println(help);
            //System.out.println(help.remove(e));
            String ch=String.valueOf(help.remove(e));
            //s.append(help.remove(e).toString());  
            s.append(ch);
        }
       return s.toString();
    }
    
    int calculateNthFactorial(int n){
        if(n==0) return 1;
        int res=n;
        while(n-1>0){
            n--;
            res*=n;
        }
        return res; 
    }
}