47. 全排列 II

难度 medium
给定一个可包含重复数字的序列 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

解题思路:这道题在20210822的时候参加美团笔试的时候遇到了,不知道是审错题目还是美团改过题目了,我总记得当时要求输出的是有序输出的,所以想了半天没有写出来,回来看了看leetcode,发现这一道题目,所以这里记一下解法,如果是简单全排列,用交换法就可以实现,要求重复的结果不要出现,因此用一个set来排除重复元素。如果真的需要有序,也许可以在全部排序之后再用一个比较器来对无重复的集合进行排序后输出,这样也可以保证结果的有序性,但是感觉成本有点高。这里只针对这道题目,给出无顺序版本。
代码

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        HashSet<List<Integer>> set = new HashSet<>();
        int len = nums.length;
        List<Integer> tmp = new ArrayList<>(len);
        for(int i=0; i<len; i++) tmp.add(nums[i]);
        dfs(set, tmp, 0);
        res.addAll(set);
        return res;
    }

    public void dfs(HashSet<List<Integer>> set, List<Integer> out, int cur){
        if(cur==out.size()){
            ArrayList<Integer> t = new ArrayList<>(out);
            set.add(t);
            return;
        }
        for(int i=cur; i<out.size(); i++){
            if(cur!=i && out.get(i)==out.get(cur)) continue;
            Collections.swap(out, i, cur);
            dfs(set, out, cur+1);
            Collections.swap(out, i, cur);
        }
    }
}

参考资料

上一篇:系统集成项目管理工程师10大管理47个过程域输入输出工具(项目沟通管理)


下一篇:剑指 Offer 47. 礼物的最大价值(中等)