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:开始用Permutation DP算法列出所有的情况，但是超时了，看了其他人的做法后，发现可以找规律～

第一次做的：

package leetcode2;
import java.util.*;
public class Permutationsequce {
   public static String getPermutation(int n, int k) {
        StringBuilder sb=new StringBuilder();
        StringBuilder sb1=new StringBuilder();
        int total=1;
        int[] num=new int[n];
        boolean[] visit =new  boolean[n];
        for(int i=n;i>0;i--){
             total=total*i;
            sb1.append(i);
            num[i-1]=i;      
        }
        if(k>=total-1){
            return sb1.toString();
        }
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> mem=new ArrayList<Integer>();
        dfs(res,mem,0,num,k,sb,visit);
        System.out.println(res);
        for(int j=0;j<res.get(k-1).size();j++){
            sb.append(res.get(k-1).get(j));
        }
        return sb.toString();
    }

private static void dfs(ArrayList<ArrayList<Integer>> res,
        ArrayList<Integer> mem, int deep, int[] n, int k,StringBuilder sb,boolean[] visit) {
    // TODO Auto-generated method stub
       if(res.size()==k){       
          return;
        }
    if(deep==n.length){
        if(!res.contains(new ArrayList<Integer>(mem))){
            res.add(new ArrayList<Integer>(mem));
            sb=new StringBuilder();
            return;
        }
    }
    if(deep<n.length){        
        for(int i=0;i<n.length;i++){
            if(!visit[i]){
            mem.add(n[i]);
            visit[i]=true;
            dfs(res,mem,deep+1,n,k,sb,visit);
            mem.remove(mem.size()-1);
            visit[i]=false;
        }
    }
    }
}
public static void main(String[] args) {
    // TODO Auto-generated method stub
 
  System.out.println(getPermutation(3,5));
}

}

正确找规律的code：

public String getPermutation(int n, int k) {  
    if(n<=0)  
        return "";  
    k--;  
    StringBuilder res = new StringBuilder();  
    int factorial = 1;  
    ArrayList<Integer> nums = new ArrayList<Integer>();  
    for(int i=2;i<n;i++)  
    {  
        factorial *= i;  
    }  
    for(int i=1;i<=n;i++)  
    {  
        nums.add(i);  
    }  
    int round = n-1;  
    while(round>=0)  
    {  
        int index = k/factorial;  
        k %= factorial;  
        res.append(nums.get(index));  
        nums.remove(index);  
        if(round>0)  
            factorial /= round;  
        round--;  
    }  
    return res.toString();  
}