leetcode47 Permutations II

taoszu 發(fā)布于2019-08-14 18:33 / 3136人閱讀

摘要：當(dāng)前的值如果已經(jīng)被使用過(guò)，則繼續(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 permutations.

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

對(duì)于其基礎(chǔ)題PermutationsI請(qǐng)參考我的另一篇博客
這里添加的難度在于，排列組合的數(shù)字中可能存在重復(fù)。這就需要想方法，將結(jié)果集中重復(fù)的結(jié)果刪去。而這里，我參考了另一名答題者的答案，在試圖將數(shù)字添入結(jié)果集中時(shí)，就判斷會(huì)不會(huì)產(chǎn)生重復(fù)的結(jié)果，從而使避免重復(fù)。

代碼和解析

這里采用了遞歸的思路。避免重復(fù)的核心思路在于，使用一個(gè)boolean數(shù)組來(lái)代表當(dāng)前的數(shù)值是否已經(jīng)被使用過(guò)。當(dāng)前的值如果已經(jīng)被使用過(guò)，則繼續(xù)判斷下一個(gè)數(shù)值。如果當(dāng)前的值為重復(fù)值，則只要前面的值沒(méi)有被使用過(guò)，則當(dāng)前值就不可以被使用。這樣確保了只有第一個(gè)出現(xiàn)的重復(fù)值可以算進(jìn)結(jié)果集，后序重復(fù)的情況不會(huì)被添加進(jìn)結(jié)果集。
例如，假設(shè)輸入的數(shù)組為[1，1，2]。則當(dāng)?shù)谝粋€(gè)1被添加進(jìn)結(jié)果集時(shí)，可以繼續(xù)使用第二個(gè)1作為元素添加進(jìn)結(jié)果集從而生成112。同理，當(dāng)試圖將第二個(gè)1作為第一個(gè)元素添加進(jìn)結(jié)果集時(shí)，只要第一個(gè)1還沒(méi)有被使用過(guò)，則不可以使用第二個(gè)1。因此，112不會(huì)被重復(fù)的添加進(jìn)結(jié)果集。
其實(shí)，這個(gè)算法保證了所有重復(fù)的數(shù)字在結(jié)果集中的順序和在原輸入數(shù)組中的順序是相同的。假設(shè)將[1,1,2]表示為[1,1#,2],那么結(jié)果集中會(huì)確保1永遠(yuǎn)在數(shù)值1#的前面，從而避免了11#2和1#12的重復(fù)情況出現(xiàn)。
代碼如下：

  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();
        //排序有利于判斷重復(fù)值
        Arrays.sort(nums);
        //深度優(yōu)先算法
        dfs(nums, used, list, res);
        return res;
    }

    public void dfs(int[] nums, boolean[] used, List list, List> res){
        //如果結(jié)果長(zhǎng)度和輸入長(zhǎng)度相等，則添加進(jìn)結(jié)果集
        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);
        }
    }

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~