Concise Java Solution withDetail Explanations


  • -1
    M

    The core idea is that denote (k-1) / (n-1)! by nth, nth represents the nth element in the candidate array should be appended to the answer string. Let's be more clear and take n = 4, k = 9 as example.

    First build you candidate array list = {1,2,3,4}; Then nth = (k-1) / (n-1)! = 8/6 = 1. which mean arrayList[1] should be removed and place to your answer string. Now answer is "2".

    Then assign k = (k-1) % (n-1)! +1 = 8%6 +1 = 3, and n= n -1 to decide the next digit. Similarly nth = (k-1) / (n-1)! = 3/2 = 1; note that now arrayList[1] = 3 since 2 has been removed in the previous iteration. Now answer is "23". Repeat that procedure until n ==0.

    public String getPermutation(int n, int k) {
    
    	int[] factorial = new int[n];
    	ArrayList<Integer> candidate = new ArrayList<Integer>();
    
        // Build factorial array
    	for (int i = 0; i < n; i++) {
    		candidate.add(i + 1);
    		factorial[i] = i == 0 ? 1 : i * factorial[i - 1];
    	}
    
    	StringBuilder sb = new StringBuilder();
    
       // Iteratively generates answer
    	while (n > 0) {
    		int remain = ((k - 1) % factorial[n - 1]) + 1;
    		sb.append(candidate.remove(((k - 1) / factorial[n - 1])));
    		n--;
    		k = remain;
    	}
    
    	return sb.toString();
    
    }

  • 0
    T

    Thank you for your sharing. But I think remove() method takes O(n) time in your case, therefore it is actually O(n^2).


  • 0
    M

    Great observation ~ Thank you very much~ I am seeking a linear time solution~


Log in to reply
 

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