47. 全排列 II(中等)

Posted on In Views:

1，问题描述

47. 全排列 II

难度：中等

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

2，初步思考

​ 与46题的唯一区别就是有重复数字！

​ 我使用了2种方法解答，一种为记录各个数字出现的频次并以map存储，遍历这个map进行回溯算法处理

​ 还有一种就是官方的处理方法变形

3，代码处理

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.*;

public class _47全排列II {

    public List<List<Integer>> permuteUnique_gov(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        Arrays.sort(nums);
        for (int num : nums) {
            output.add(num);
        }
        backtrack(len, 0, output, res);
        return res;
    }

    private void backtrack(int len, int index, List<Integer> output, List<List<Integer>> res) {
        if (index == len) res.add(new ArrayList<>(output));
        Set<Integer> set = new HashSet<>();
        for (int i = index; i < len; i++) {
            if (set.contains(output.get(i))) {// 已经使用过的数据直接跳过即可
                continue;
            }
            set.add(output.get(i));
            Collections.swap(output, index, i);// 交换位置，递归处理
            backtrack(len, index + 1, output, res);
            Collections.swap(output, index, i);// 恢复原样
        }
    }

    // 输出全排列
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 1,统计各个kv的数据
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        // 2，开始进行遍历处理
        ArrayList<Integer> keys = new ArrayList<>(map.keySet());
        for (Integer key : keys) {// 遍历这一个层级的key
            List<Integer> list = new ArrayList<>();
            list.add(key);
            update(res, list, key, map);
        }

        // 3，返回结果
        return res;
    }

    private void update(List<List<Integer>> res, List<Integer> list, int key, Map<Integer, Integer> map) {
        // 2.1，更新map
        Integer counter = map.get(key);
        if (counter <= 1) {
            map.remove(key);
        } else {
            map.put(key, counter - 1);
        }

        // 2.2，检查退出条件
        if (map.isEmpty()) {
            res.add(list);
            map.put(key, 1);// 恢复数据
            return;
        }

        // 2.3，遍历下一层
        ArrayList<Integer> keys = new ArrayList<>(map.keySet());
        for (Integer nextKey : keys) {
            List<Integer> listCur = new ArrayList<>(list);
            listCur.add(nextKey);
            update(res, listCur, nextKey, map);
        }

        // 2.4，恢复map
        map.put(key, counter);
    }

    public static void main(String[] args) {
        _47全排列II permutation = new _47全排列II();
//        System.out.println(permutation.permuteUnique_gov(new int[]{1, 1, 2}));
//        System.out.println(permutation.permuteUnique_gov(new int[]{0, 1, 0, 0, 9}));
        System.out.println(permutation.permuteUnique_gov(new int[]{-1, 2, 0, -1, 1, 0, 1}));
//        System.out.println(permutation.permuteUnique_gov(new int[]{1, 2, 3}));
    }
}

参考链接：

46. 全排列