60. Permutation Sequence Leetcode Java

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:

This problem is about to find the pattern behind the permutation sequence. There are total n! of unique permutations. The first number has n choices and the second one has n-1 options...., so we have to decide which one is the first choice and which one is chosen to be the second one... Basically, we have a sorted arraylist, each time we gonna pick one according to our pattern I will discuss later, and remove this picked one, then picked the next one until to the last one. The pattern is that, since there are n options for the first digit, the first (n-1)! of permutations among all the n! permutations will pick the first number as their first digits, and next (n-1)! of permutations will pick the second number as their first digits...

So for the kth permuation we can determine the first digit by divided k by (n-1)!, then we pick that number, and remove it from the list, the problem becomes find the ((k%(n-1))+1)th permutation for (n-1) number available... keep find the right number until only one number left.

  public String getPermutation(int n, int k) {  
    if(k==0) return "";  
    ArrayList<Integer> num=new ArrayList<Integer>();  
    int factor=1;  
    for(int i=1;i<=n;i++) {  
      num.add(i);  
      factor*=i;  
    }  
    factor=factor/n;  
    StringBuilder sb=new StringBuilder();  
    while(n>1){  
      int ind=(k-1)/(factor);  
      sb.append(num.get(ind));  
      num.remove(ind);  
      n--;  
      k=(k-1)%factor+1;  
      factor=factor/n;  
    }  
    sb.append(num.get(0));  
    return sb.toString();  
   }