国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode 47 Permutations II

Cobub / 1331人閱讀

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

題目詳情 
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
題目要求輸入一個(gè)可能會(huì)有重復(fù)數(shù)字的數(shù)組nums，要求我們輸出nums可能組成的全排列（無重復(fù)排列）。
思路

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

一種思路就是我在沒次為我的結(jié)果集res添加新的排列的時(shí)候 判斷新添加的排列 是否已經(jīng)存在于結(jié)果集中了?？梢杂胔ashset來實(shí)現(xiàn)，但這種實(shí)現(xiàn)方式復(fù)雜度高。

另外一種實(shí)現(xiàn)思路是，新聲明一個(gè)boolean數(shù)組isUsed來存儲(chǔ)nums中元素的使用狀況。然后在生成當(dāng)前排列curr的時(shí)候就避免重復(fù)排列的產(chǎn)生。

以[1,1*,2]這個(gè)數(shù)組為例。

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

解法 
    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);
        }
    }

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/71098.html

相關(guān)文章

  • leetcode47 Permutations II

    摘要：當(dāng)前的值如果已經(jīng)被使用過，則繼續(xù)判斷下一個(gè)數(shù)值。則當(dāng)?shù)谝粋€(gè)被添加進(jìn)結(jié)果集時(shí)，可以繼續(xù)使用第二個(gè)作為元素添加進(jìn)結(jié)果集從而生成。假設(shè)將表示為那么結(jié)果集中會(huì)確保永遠(yuǎn)在數(shù)值的前面，從而避免了和的重復(fù)情況出現(xiàn)。 題目要求 Given a collection of numbers that might contain duplicates, return all possible unique ...

    taoszu 評論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...

    leo108 評論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 評論0 收藏0

  • [Leetcode] Permutations 全排列

    摘要：每一輪搜索選擇一個(gè)數(shù)加入列表中，同時(shí)我們還要維護(hù)一個(gè)全局的布爾數(shù)組，來標(biāo)記哪些元素已經(jīng)被加入列表了，這樣在下一輪搜索中要跳過這些元素。 Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permu...

    scq000 評論0 收藏0

  • [Leetcode]PermutationsI II Next Permutation Permut

    摘要：解題思路這道題是要將排列按字典序排列，然后求出下一個(gè)排列，一種辦法是我們先求出所有的排序情況，但是題目規(guī)定不能占有額外空間。每次求出一個(gè)數(shù)字后，要及時(shí)的把它從中刪除掉。采用來構(gòu)造結(jié)果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...

    ChristmasBoy 評論0 收藏0

發(fā)表評論

0條評論

Cobub

男|高級講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<