LeetCode46-全排列

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/permutations/

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

题目详述

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题目详解

DFS，回溯。

  • 每次尝试固定一个位置，然后进入下一层。
  • 回到本层时恢复原状。
  • 递归的终止条件是当前固定位置的下标为 nums.length，将这个排列加入结果集中。
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
public class LeetCode_00046 {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, res, 0);
        return res;
    }

    private void dfs(int[] nums, List<List<Integer>> res, int s) {
        if (s == nums.length) {
            List<Integer> list = new ArrayList<>(nums.length);
            for (int num : nums) {
                list.add(num);
            }
            res.add(list);
            return;
        }
        for (int i = s; i < nums.length; ++i) {
            swap(nums, i, s);
            dfs(nums, res, s + 1);
            swap(nums, i, s);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

也可以按照全排列的生成规则直接得到下一个排列。

  • 首先按照从小到大的顺序进行排序，得到第一个排列。

  • 从后往前找到第一组位置，满足 nums[i] < nums[i + 1]。找不到说明已经是最后一个排列，返回 false。

  • 从后往前找到第一个位置，满足 nums[i] < nums[j]。
  • 交换 i、j 两处的值。
  • 反转从位置 i + 1 到末尾的序列，得到下一个排列，返回 true。
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
41
42
43
44
45
46
47
48
public class LeetCode_00046 {

    public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        do {
            List<Integer> list = new ArrayList<>(nums.length);
            for (int num : nums) {
                list.add(num);
            }
            res.add(list);
        } while (nextPermutation(nums));
        return res;
    }

    private boolean nextPermutation(int[] nums) {
        // 1. 从后往前找到第一组位置，满足 nums[i] < nums[i + 1]
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i >= 0) {
            // 2. 从后往前找到第一个位置，满足 nums[i] < nums[j]
            int j = nums.length - 1;
            while (nums[i] >= nums[j]) {
                --j;
            }
            // 3. 交换 i、j 两处的值
            swap(nums, i, j);
            // 4. 反转从位置 i + 1 到末尾的序列
            reverse(nums, i + 1, nums.length - 1);
            return true;
        }
        return false;
    }

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

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}