leetcode 47 Permutations II

Cobub 發布于2019-08-16 11:13 / 1327人閱讀

摘要：題目詳情題目要求輸入一個可能會有重復數字的數組，要求我們輸出可能組成的全排列無重復排列。可以用來實現，但這種實現方式復雜度高。另外一種實現思路是，新聲明一個數組來存儲中元素的使用狀況。以這個數組為例。

題目詳情

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
題目要求輸入一個可能會有重復數字的數組nums，要求我們輸出nums可能組成的全排列（無重復排列）。

思路

這道題和 46題全排列的差別就在于它可能存在重復數字，所以我們就要考慮重復數字可能造成的重復排列的問題。

一種思路就是我在沒次為我的結果集res添加新的排列的時候判斷新添加的排列是否已經存在于結果集中了。可以用hashset來實現，但這種實現方式復雜度高。

另外一種實現思路是，新聲明一個boolean數組isUsed來存儲nums中元素的使用狀況。然后在生成當前排列curr的時候就避免重復排列的產生。

以[1,1*,2]這個數組為例。

對于每次遍歷的元素nums[i]，我們要判斷它是否等于nums[i-1]，如果相等而且nums[i-1]被使用過的話，就可以組成一個未出現的排序(eg.[1，1])，如果nums[i-1]未被使用過，那么我們不會將nums[i]添加進排列，避免產生[1,1]這樣的重復排列。

解法

    public List> permuteUnique(int[] nums) {
        
        List> res = new ArrayList>();
        boolean[] isUsed = new boolean[nums.length];
        List curr = new ArrayList();
        Arrays.sort(nums);
        backtrack(res,isUsed,curr,nums);       

        return res;
    }
    
    public void backtrack(List> res,boolean[] isUsed,List curr,int[] nums){
        
        if(nums.length == curr.size()){
            res.add(new ArrayList(curr));
            return;
        }
        
        for(int i=0;i0 && nums[i] == nums[i-1] && !isUsed[i-1])continue;
            isUsed[i] = true;
            curr.add(nums[i]);
            backtrack(res,isUsed,curr,nums);
            isUsed[i] = false;
            curr.remove(curr.size()-1);
        }
    }

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71098.html

leetcode47 Permutations II

摘要：當前的值如果已經被使用過，則繼續判斷下一個數值。則當第一個被添加進結果集時，可以繼續使用第二個作為元素添加進結果集從而生成。假設將表示為那么結果集中會確保永遠在數值的前面，從而避免了和的重復情況出現。題目要求 Given a collection of numbers that might contain duplicates, return all possible unique ...

taoszu 2019-08-14 18:33 評論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