Permutation Sequence Solution


  • 0
    A

    A string which has n length has n! full permutation. The question means acquiring the kth permutation.

    I list an easy example below:

    Precondition:
    the string is "1234", and the full permutation is below:
    1234
    1243
    1324
    1342
    1423
    1432
    2134
    2143
    2314
    2341
    2413
    2431
    3124
    3142
    3214
    3241
    3412
    3421
    4123
    4132
    4213
    4231
    4312
    4321

    Based on what I list above, we can find that each number appears 6 times. What`s more, if the first number is confirmed, the other numbers will appear only 2 times, when the second number is confirmed, the extra numbers will just appear one times. So the we can follow the principle and write the code:

    class Solution {
        public String getPermutation(int n, int k) {
    		if (n <= 0) {
    			return null;
    		}
    		if (n == 1) {
    			return String.valueOf(n);
    		}
    		List<Integer> temp = new ArrayList<Integer>();
    		for (int i = 1; i <= n; i++) {
    			temp.add(i);
    		}
    		int pCount = 1;
    		for (int i = 1; i <= n; i++) {
    			pCount = pCount * i;
    		}
    		if(k > pCount){
    			return null;
    		}
    		k--;
    		StringBuilder result = new StringBuilder();
    		for (int i = 0; i < n; i++) {
    			pCount = pCount / (n - i);
    			int selected = k / pCount;
    			result.append(temp.get(selected));
    			temp.remove(selected);
    			k = k % pCount;
    		}
    		return result.toString();
        }
    }
    

Log in to reply
 

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