leetcode47-全排列II

原题

给定一个可包含重复数字的序列,返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解法

思想

这道题和leetcode46-全排列的区别在于,数组中会出现相同的数字,对于搜索来说,我们把它想象成树的DFS搜索,就应该避免在同一层搜索到相同值的节点,而不同层之间是允许存在相同值节点的。

我们使用上道题的代码进行改造,如下所示:

代码

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    int[] nums;
    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        this.nums = nums;
        //要去重,先排序
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        dfs(list,used,0);
        return ans;
    }
    public void dfs(List<Integer> list,int[] used,int usedCount){
        if(usedCount==nums.length){
            ans.add(list);
        }
        for(int i = 0;i<nums.length;i++){
            // i == 0,前面没有元素,可以搜索
            // used[i-1] == 0,前面的元素在别的层级用过了,可以搜索
            // nums[i]!=nums[i-1],前面的元素和当前元素不相同,可以搜索
            if(used[i]==0 && (i == 0 || used[i-1] ==1 || nums[i]!=nums[i-1])){
                List<Integer> copy = new ArrayList<>(list);
                copy.add(nums[i]);
                int[] usedCopy = Arrays.copyOf(used,used.length);
                usedCopy[i] = 1;
                dfs(copy,usedCopy,usedCount+1);
            }
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode47-%e5%85%a8%e6%8e%92%e5%88%97ii/

发表回复

登录后才能评论