My Java Iterative Solution with Explaination


  • 0
    Z

    I select each number by iteration. In other to store 1 to n numbers, I create a ArrayList for removing convenience.

    Taking n=3 for example, the first number has three choices 1,2,3, so we can divide the six sequences into three different parts based on the first number. 6/3 = 2 =factorial(n-1). That's why I calculate (k-1)/factorial to determine which parts kth sequence belong.

    After we get the first number, we need to update n, k and remove the selected number from ArrayList, then go to select the next number.

    public class Solution {
    	public String getPermutation(int n, int k) {
    		List<Integer> L = new ArrayList<Integer>();
    		for(int i=1; i<=n; i++){
    			L.add(i);
    		}
    		return helper(n, k, L);
    	}
    	public String helper(int n, int k, List<Integer> L){
    		String res = "";
    		while(n>0){
    			int factorial = 1;
    			for(int i=1; i<=n-1; i++){
    				factorial *= i;
    			}
    			int t = L.get((k-1)/factorial);
    			L.remove((k-1)/factorial);
    			res += Integer.toString(t);
    			k = (k-factorial*((k-1)/factorial));
    			n--;
    		}
    		return res;		
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.