Leetcode 60 Permutation Sequence

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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Solution 1: the kth number is a0,a1,a2..an-1; the weight for a0 is (n-1)!, a1 is (n-2)! ...an-1 is 0!. When build the result, each time select the num from the list of nums remaining and in order. The selection is based on how many time of the weight. Code as below:

 public class Solution {  
   public String getPermutation(int n, int k) {  
     if (n<1 || k<1) return "";  
     List<Integer> nums=new LinkedList<>();//put all avalibale nums in a list  
     for (int i=1; i<=n; i++) nums.add(i);  
     int[] p=new int[n+1]; //store p[i]=i!, so do not need repeate calculation  
     for (int i=0; i<=n; i++) {  
       if (i==0) p[i]=1;  
       else p[i]=i*p[i-1];  
     }  
     k--; k%=p[n];  
     StringBuilder res=new StringBuilder();  
     for (int i=n-1; i>=0; i--) {  
       int num=nums.get(k/p[i]);  
       res.append(String.valueOf(num));  
       nums.remove(new Integer(num));//remove the num object not index  
       k=k%p[i];  
     }  
     return res.toString();  
   }  
 }