[LeetCode] 60. Permutation Sequence

Posted on | In

Problem

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:

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

Example 2:

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

Explanation

  1. For example, when n=4, k=9:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
     1234
 1243
 1324
 1342
 1423
 1432
 2134
 2143
 2314  <= k = 9
 2341
 2413
 2431
 3124
 3142
 3214
 3241
 3412
 3421
 4123
 4132
 4213
 4231
 4312
 4321

  2. The most significant digit can be choosen from {1, 2, 3, 4}, and each number in the most significant digit is repeated (n-1)! = 6 times. So, in the result, the most significant digit will be the second (res[0] = 9 / 6 + 1 = 2) number, which is 2.

  3. Now we know the result’s most significant digit is the number 2, then we need to find out what’s the number for the second most significant digit, and we can only choose from number {1, 3, 4} in these 6 (3!) numbers: 2134, 2143, 2314, 2341, 2413, 2431. k is 9, now the new k' will become 9 % (3!) = 9 % 6 = 3. And each number {1, 3, 4} in the second most significant digit is repeated (n-2)! = 2 times. So, in the result, the second most significant digit will be the second (res[1] = 3 / 2 + 1 = 2) number, which is 3.

  4. Now we know the result is starting from 23, and we can only choose from number {1, 4} in these 2 (2!) numbers: 2314, 2341. k' is 3, now the new k'' will become 3 % (2!) = 3 % 2 = 1. And each number {1, 4} in the third most significant digit is appear (n-3)! = 1 time. So, in the result, the third most significant digit will be the first number, which is 1.

  5. Now we know the result is starting from 231, and there is only {4} left, so the last digit is 4, and the result will be 2314.

  6. Basically, after we find out the most significant digit by doing k / fac[i], then we need to find out the new k in the next most significant digit by doing k % fac[i], and repeat the process.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i-1] * i;
        }
        List<Integer> num = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            num.add(i);
        }

        k -= 1; // start with index 0
        StringBuilder sb = new StringBuilder();
        for (int i = n-1; i >= 0; i--) {
            int c = k / factorial[i];
            sb.append(num.remove(c));
            k = k % factorial[i];
        }

        return sb.toString();
    }
}