leetcode 47. Permutations II 全排列 II(中等)

作者：okokabcd

2022 年 6 月 12 日
本文字数：831 字
阅读完需：约 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 是元素的个数，然后再用回溯法来解决

三、解题方法

3.1 Java 实现

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();            }        }    }}

复制代码

四、总结小记

2022/6/12 来记录结果的类型要用双端队列

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/08c136572c44ab06e4d8d8a4d】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

一年当十年用的Java程序员

发布

暂无评论

创作场景