Clean Java Solution


  • 9
    M

    The basic idea is to decide which is the correct number starting from the highest digit.
    Use k divide the factorial of (n-1), the result represents the ith not used number.
    Then update k and the factorial to decide next digit.

    public String getPermutation(int n, int k) {

       LinkedList<Integer> notUsed = new LinkedList<Integer>();
    
    	int weight = 1;
    
    	for (int i = 1; i <= n; i++) {
    		notUsed.add(i);
    		if (i == n)
    			break;
    		weight = weight * i;
    	}
    
    	String res = "";
    	k = k - 1;
    	while (true) {
    		res = res + notUsed.remove(k / weight);
    		k = k % weight;
    		if (notUsed.isEmpty())
    			break;
    		weight = weight / notUsed.size();
    	}
    
    	return res;
    }

Log in to reply
 

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