LeetCode 60. Permutation Sequence

60. Permutation Sequence

Difficulty: Medium

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 for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Solution

Language: Java

class Solution {
    public String getPermutation(int n, int k) {
        if (n == 0) {
            return "";
        }
        if (n == 1) {
            return "1";
        }
        int fact = 1;
        int end = n - 1;
        for (int i = 2; i <= end; i++) {
            fact *= i;
        }
        StringBuilder sb = new StringBuilder();
        List<Integer> list = new ArrayList<>(n);
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        k--;
        while (sb.length() != n) {
            int index = k / fact;
            sb.append(list.get(index));
            list.remove(index);
            k %= fact;
            if (end != 0) {
                fact /= end;
            }
            end--;
        }
        return sb.toString();
    }
}