Leetcode(60) Permutation Sequence

发表于 | 更新于 | 分类于

Description:

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”

解法：

这道题主要是找规律，因为不必要把所有的排列都列出来，所以以 n = 4 k = 17为例：

首先我们要知道当n = 3时，其排列组合共有3! = 6种，当n = 4时，其排列组合共有4! = 24种，所有排列组合情况如下：

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <— k = 17
3421
4123
4132
4213
4231
4312
4321

我们可以发现，每一位上1,2,3,4分别都出现了6次，当最高位上的数字确定了，第二高位每个数字都出现了2次，当第二高位也确定了，第三高位上的数字都只出现了1次，当第三高位确定了，那么第四高位上的数字也只能出现一次，下面我们来看k = 17这种情况的每位数字如何确定，由于k = 17是转化为数组下标为16：

最高位可取1,2,3,4中的一个，每个数字出现3！= 6次，所以k = 16的第一位数字的下标为16 / 6 = 2，在 “1234” 中即3被取出。这里我们的k是要求的坐标为k的全排列序列，我们定义 k’ 为当最高位确定后，要求的全排序列在新范围中的位置，同理，k” 为当第二高为确定后，所要求的全排列序列在新范围中的位置，以此类推，下面来具体看看：

第二位此时从1,2,4中取一个，k = 16，则此时的 k’ = 16 % (3!) = 4，如下所示，而剩下的每个数字出现2！= 2次，所以第二数字的下标为4 / 2 = 2，在 “124” 中即4被取出。

3124
3142
3214
3241
3412 <— k’ = 4
3421

第三位此时从1,2中去一个，k’ = 4，则此时的k” = 4 % (2!) = 0，如下所示，而剩下的每个数字出现1！= 1次，所以第三个数字的下标为 0 / 1 = 0，在 “12” 中即1被取出。

3412 <— k” = 0
3421

第四位是从2中取一个，k” = 0，则此时的k”’ = 0 % (1!) = 0，如下所示，而剩下的每个数字出现0！= 1次，所以第四个数字的下标为0 / 1= 0，在 “2” 中即2被取出。

3412 <— k”’ = 0

那么我们就可以找出规律了
a1 = k / (n – 1)!
k1 = k

a2 = k1 / (n – 2)!
k2 = k1 % (n – 2)!
…

an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!

an = kn-1 / 0!
kn = kn-1 % 0!

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder nums = new StringBuilder("123456789");
        StringBuilder res = new StringBuilder();
        int[] array = new int[n + 1];
        array[0] = 1;
        for (int i = 1; i <= n; i++) {
            array[i] = array[i - 1] * i;
        }
        k -= 1;
        n -= 1;
        while (n >= 1) {
            int s = k / array[n];
            res.append(nums.charAt(s));
            nums.deleteCharAt(s);
            k = k % array[n];
            n--;
        }
        res.append(nums.charAt(0));
        return res.toString();
    }
}