LeetCode60-第k个排列

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/permutation-sequence/

中文链接：https://leetcode-cn.com/problems/permutation-sequence/

题目详述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

给定 n 和 k，返回第 k 个排列。

说明：

  • 给定 n 的范围是 [1, 9]。
  • 给定 k 的范围是[1, n!]。

示例 1:

1
2
输入: n = 3, k = 3
输出: "213"

示例 2:

1
2
输入: n = 4, k = 9
输出: "2314"

题目详解

  • 可以按顺序求出第 k 个排列。
  • 时间复杂度为 O(k)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class LeetCode_00060 {

    public String getPermutation(int n, int k) {
        char[] cs = new char[n];
        for (int i = 0; i < n; ++i) {
            cs[i] = (char) ('1' + i);
        }
        while (--k > 0) {
            nextPermutation(cs, n);
        }
        return String.valueOf(cs);
    }

    private void nextPermutation(char[] cs, int n) {
        int i = n - 2;
        while (i >= 0 && cs[i] >= cs[i + 1]) {
            --i;
        }
        if (i >= 0) {
            int j = n - 1;
            while (cs[i] >= cs[j]) {
                --j;
            }
            swap(cs, i, j);
            reverse(cs, i + 1, n - 1);
        }
    }

    private void reverse(char[] cs, int i, int j) {
        while (i < j) {
            swap(cs, i++, j--);
        }
    }

    private void swap(char[] cs, int i, int j) {
        char tmp = cs[i];
        cs[i] = cs[j];
        cs[j] = tmp;
    }
}
  • 实际上，可以不用按顺序求出每一个排列，可以直接跳过前面的排列。当某一位确定后，可以知道有多少种排列，处于前面的排列可以不用求，然后再确定下一位。
  • 从高位到低位考虑，对于每一位，从未使用过的数中确定当前位是几。
  • 以 n = 4，k = 14 为例：
    1. 1 + (2、3、4 的排列）
    2. 2 + (1、3、4 的排列）
    3. 3 + (1、2、4 的排列）
    4. 4 + (1、2、3 的排列）
  • 每组的排列个数为 3! = 6 个，显然第 14 个排列在第 3 组中，所以第 1 位是 3。接下来确定后面的位，即在 1、2、4 的排列中找第 14 - 6 * 2 = 2 个排列。
  • 因为 2! = 2，2 / 2 = 1，2 - 2 * 0 = 2，所以确定处于第 1 组中，即这一位为 1。接下来在 2、4 的排列中找第 2 个排列。
  • 因为 1! = 1，2 / 1 = 2，2 - 1 * 1 = 1，所以确定处于第 2 组中，即这一位为 4。接下来在 2 的排列中找第 1 个排列。
  • 逐位得出第 14 个排列为 3142。
  • 时间复杂度为 O(n^2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00060 {

    public String getPermutation(int n, int k) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            list.add(i);
        }
        int[] f = new int[n];
        f[0] = 1;
        for (int i = 1; i < n; ++i) {
            f[i] = f[i - 1] * i;
        }
        --k;
        StringBuilder sb = new StringBuilder(n);
        for (int i = n - 1; i >= 0; --i) {
            int j = k / f[i];
            k %= f[i];
            sb.append(list.remove(j));
        }
        return sb.toString();
    }
}