关于leetcode:leetcode-47-Permutations-II-全排列-II中等

6次阅读

共计 1084 个字符，预计需要花费 3 分钟才能阅读完成。

标签: 搜寻

https://leetcode.cn/problems/permutations-ii

给定一个可蕴含反复数字的序列 nums，按任意程序返回所有不反复的全排列。
示例 1：

输出：nums = [1,1,2]
输入：
[[1,1,2],
[1,2,1],
[2,1,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

二、解题思路

用回溯法解决全排列问题，给定的数组中元素有反复，因而用回溯法执行后的全排列后果中会有反复的，如下图所示。

解决办法，先结构一个 hashmap，key 是元素，value 是元素的个数，而后再用回溯法来解决

public class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> ans = new ArrayList<>();
        // 结构一个 hashmap
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int n : nums) {int count = countMap.getOrDefault(n, 0);
            countMap.put(n, count + 1);
        }
        dfs(countMap, nums.length, new LinkedList<>(), ans);
        return ans;
    }

    void dfs(Map<Integer, Integer> countMap, int total, Deque<Integer> perm, List<List<Integer>> ans) {
        // 应用双端队列
        if (perm.size() == total) {ans.add(new ArrayList<>(perm));
        }
        for (Map.Entry<Integer, Integer> tmp : countMap.entrySet()) {if (tmp.getValue() > 0) {int oldValue = tmp.getValue();
                perm.offerFirst(tmp.getKey());
                tmp.setValue(tmp.getValue() - 1);
                dfs(countMap, total, perm, ans);
                tmp.setValue(oldValue);
                perm.pollFirst();}
        }
    }
}