leetcode47 Permutations II

taoszu 發布于2019-08-14 18:33 / 3132人閱讀

摘要：當前的值如果已經被使用過，則繼續判斷下一個數值。則當第一個被添加進結果集時，可以繼續使用第二個作為元素添加進結果集從而生成。假設將表示為那么結果集中會確保永遠在數值的前面，從而避免了和的重復情況出現。

題目要求

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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