leetcode47 Permutations II

taoszu 发布于2019-08-14 18:33 / 3095人阅读

摘要：当前的值如果已经被使用过，则继续判断下一个数值。则当第一个被添加进结果集时，可以继续使用第二个作为元素添加进结果集从而生成。假设将表示为那么结果集中会确保永远在数值的前面，从而避免了和的重复情况出现。

题目要求

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

对于其基础题PermutationsI请参考我的另一篇博客
这里添加的难度在于，排列组合的数字中可能存在重复。这就需要想方法，将结果集中重复的结果删去。而这里，我参考了另一名答题者的答案，在试图将数字添入结果集中时，就判断会不会产生重复的结果，从而使避免重复。

代码和解析

这里采用了递归的思路。避免重复的核心思路在于，使用一个boolean数组来代表当前的数值是否已经被使用过。当前的值如果已经被使用过，则继续判断下一个数值。如果当前的值为重复值，则只要前面的值没有被使用过，则当前值就不可以被使用。这样确保了只有第一个出现的重复值可以算进结果集，后序重复的情况不会被添加进结果集。
例如，假设输入的数组为[1，1，2]。则当第一个1被添加进结果集时，可以继续使用第二个1作为元素添加进结果集从而生成112。同理，当试图将第二个1作为第一个元素添加进结果集时，只要第一个1还没有被使用过，则不可以使用第二个1。因此，112不会被重复的添加进结果集。
其实，这个算法保证了所有重复的数字在结果集中的顺序和在原输入数组中的顺序是相同的。假设将[1,1,2]表示为[1,1#,2],那么结果集中会确保1永远在数值1#的前面，从而避免了11#2和1#12的重复情况出现。
代码如下：

  public List> permuteUnique(int[] nums) {
        List> res = new ArrayList>();
        if(nums==null || nums.length==0) return res;
        boolean[] used = new boolean[nums.length];
        List list = new ArrayList();
        //排序有利于判断重复值
        Arrays.sort(nums);
        //深度优先算法
        dfs(nums, used, list, res);
        return res;
    }

    public void dfs(int[] nums, boolean[] used, List list, List> res){
        //如果结果长度和输入长度相等，则添加进结果集
        if(list.size()==nums.length){
            res.add(new ArrayList(list));
            return;
        }
        for(int i=0;i0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
            used[i]=true;
            list.add(nums[i]);
            dfs(nums,used,list,res);
            used[i]=false;
            list.remove(list.size()-1);
        }
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 Permutations Leetcod LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67086.html

leetcode 47 Permutations II

摘要：题目详情题目要求输入一个可能会有重复数字的数组，要求我们输出可能组成的全排列无重复排列。可以用来实现，但这种实现方式复杂度高。另外一种实现思路是，新声明一个数组来存储中元素的使用状况。以这个数组为例。题目详情 Given a collection of numbers that might contain duplicates, return all possible unique ...

Cobub 2019-08-16 11:13 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LeetCode] Permutations I / II

Permutations I Problem Given a list of numbers, return all possible permutations. Example For nums = [1,2,3], the permutations are: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] Challe...

shery 2019-08-14 15:14 评论0 收藏0
[Leetcode] Permutations 全排列

摘要：每一轮搜索选择一个数加入列表中，同时我们还要维护一个全局的布尔数组，来标记哪些元素已经被加入列表了，这样在下一轮搜索中要跳过这些元素。 Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permu...

scq000 2019-08-14 12:31 评论0 收藏0
[Leetcode]PermutationsI II Next Permutation Permut

摘要：解题思路这道题是要将排列按字典序排列，然后求出下一个排列，一种办法是我们先求出所有的排序情况，但是题目规定不能占有额外空间。每次求出一个数字后，要及时的把它从中删除掉。采用来构造结果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

ChristmasBoy 2019-08-16 10:26 评论0 收藏0