日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
排列問(wèn)題也要去重了！

全排列 II

力扣題目鏈接：https://leetcode-cn.com/problems/permutations-ii

創(chuàng)新互聯(lián)-專(zhuān)業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比姜堰網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式姜堰網(wǎng)站制作公司更省心,省錢(qián),快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋姜堰地區(qū)。費(fèi)用合理售后完善，10年實(shí)體公司更值得信賴(lài)。

給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ，按任意順序 返回所有不重復(fù)的全排列。

示例 1：

  • 輸入：nums = [1,1,2]
  • 輸出：[[1,1,2], [1,2,1], [2,1,1]]

示例 2：

  • 輸入：nums = [1,2,3]
  • 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

思路

如果對(duì)回溯算法基礎(chǔ)還不了解的話，我還特意錄制了一期視頻：帶你學(xué)透回溯算法(理論篇) 可以結(jié)合題解和視頻一起看，希望對(duì)大家理解回溯算法有所幫助。

這道題目和全排列的區(qū)別在與給定一個(gè)可包含重復(fù)數(shù)字的序列，要返回所有不重復(fù)的全排列。

這里又涉及到去重了。

在組合總和II 、子集II我們分別詳細(xì)講解了組合問(wèn)題和子集問(wèn)題如何去重。

那么排列問(wèn)題其實(shí)也是一樣的套路。

還要強(qiáng)調(diào)的是去重一定要對(duì)元素經(jīng)行排序，這樣我們才方便通過(guò)相鄰的節(jié)點(diǎn)來(lái)判斷是否重復(fù)使用了。

我以示例中的 [1,1,2]為例 (為了方便舉例，已經(jīng)排序)抽象為一棵樹(shù)，去重過(guò)程如圖：

全排列II1

圖中我們對(duì)同一樹(shù)層，前一位(也就是nums[i-1])如果使用過(guò)，那么就進(jìn)行去重。

一般來(lái)說(shuō)：組合問(wèn)題和排列問(wèn)題是在樹(shù)形結(jié)構(gòu)的葉子節(jié)點(diǎn)上收集結(jié)果，而子集問(wèn)題就是取樹(shù)上所有節(jié)點(diǎn)的結(jié)果。

在46.全排列中已經(jīng)詳解講解了排列問(wèn)題的寫(xiě)法，在40.組合總和II 、90.子集II中詳細(xì)講解的去重的寫(xiě)法，所以這次我就不用回溯三部曲分析了，直接給出代碼，如下：

C++代碼

 
 
 
 
      
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2. private: 
    3.   
  
  
  
  3.     vector> result; 
    4.   
  
  
  
  4.     vector path; 
    5.   
  
  
  
  5.     void backtracking (vector& nums, vector& used) { 
    6.   
  
  
  
  6.         // 此時(shí)說(shuō)明找到了一組 
    7.   
  
  
  
  7.         if (path.size() == nums.size()) { 
    8.   
  
  
  
  8.             result.push_back(path); 
    9.   
  
  
  
  9.             return; 
    10.   
  
  
  
  10.         } 
    11.   
  
  
  
  11.         for (int i = 0; i < nums.size(); i++) { 
    12.   
  
  
  
  12.             // used[i - 1] == true，說(shuō)明同一樹(shù)支nums[i - 1]使用過(guò) 
    13.   
  
  
  
  13.             // used[i - 1] == false，說(shuō)明同一樹(shù)層nums[i - 1]使用過(guò) 
    14.   
  
  
  
  14.             // 如果同一樹(shù)層nums[i - 1]使用過(guò)則直接跳過(guò) 
    15.   
  
  
  
  15.             if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    16.   
  
  
  
  16.                 continue; 
    17.   
  
  
  
  17.             } 
    18.   
  
  
  
  18.             if (used[i] == false) { 
    19.   
  
  
  
  19.                 used[i] = true; 
    20.   
  
  
  
  20.                 path.push_back(nums[i]); 
    21.   
  
  
  
  21.                 backtracking(nums, used); 
    22.   
  
  
  
  22.                 path.pop_back(); 
    23.   
  
  
  
  23.                 used[i] = false; 
    24.   
  
  
  
  24.             } 
    25.   
  
  
  
  25.         } 
    26.   
  
  
  
  26.     } 
    27.   
  
  
  
  27. public: 
    28.   
  
  
  
  28.     vector> permuteUnique(vector& nums) { 
    29.   
  
  
  
  29.         result.clear(); 
    30.   
  
  
  
  30.         path.clear(); 
    31.   
  
  
  
  31.         sort(nums.begin(), nums.end()); // 排序 
    32.   
  
  
  
  32.         vector used(nums.size(), false); 
    33.   
  
  
  
  33.         backtracking(nums, used); 
    34.   
  
  
  
  34.         return result; 
    35.   
  
  
  
  35.     } 
    36.   
  
  
  
  36. }; 
    37.

拓展

大家發(fā)現(xiàn)，去重最為關(guān)鍵的代碼為：

 
 
 
 
      
  
  
  
  1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    2.   
  
  
  
  2.     continue; 
    3.   
  
  
  
  3. } 
    4.

如果改成 used[i - 1] == true， 也是正確的!，去重代碼如下：

 
 
 
 
      
  
  
  
  1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) { 
    2.   
  
  
  
  2.     continue; 
    3.   
  
  
  
  3. } 
    4.

這是為什么呢，就是上面我剛說(shuō)的，如果要對(duì)樹(shù)層中前一位去重，就用used[i - 1] == false，如果要對(duì)樹(shù)枝前一位去重用used[i - 1] == true。

對(duì)于排列問(wèn)題，樹(shù)層上去重和樹(shù)枝上去重，都是可以的，但是樹(shù)層上去重效率更高!

這么說(shuō)是不是有點(diǎn)抽象?

來(lái)來(lái)來(lái)，我就用輸入: [1,1,1] 來(lái)舉一個(gè)例子。

樹(shù)層上去重(used[i - 1] == false)，的樹(shù)形結(jié)構(gòu)如下：

全排列II2

樹(shù)枝上去重(used[i - 1] == true)的樹(shù)型結(jié)構(gòu)如下：

全排列II

大家應(yīng)該很清晰的看到，樹(shù)層上對(duì)前一位去重非常徹底，效率很高，樹(shù)枝上對(duì)前一位去重雖然最后可以得到答案，但是做了很多無(wú)用搜索。

總結(jié)

這道題其實(shí)還是用了我們之前講過(guò)的去重思路，但有意思的是，去重的代碼中，這么寫(xiě)：

 
 
 
 
      
  
  
  
  1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { 
    2.   
  
  
  
  2.     continue; 
    3.   
  
  
  
  3. } 
    4.

和這么寫(xiě)：

 
 
 
 
      
  
  
  
  1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) { 
    2.   
  
  
  
  2.     continue; 
    3.   
  
  
  
  3. } 
    4.

都是可以的，這也是很多同學(xué)做這道題目困惑的地方，知道used[i - 1] == false也行而used[i - 1] == true也行，但是就想不明白為啥。

所以我通過(guò)舉[1,1,1]的例子，把這兩個(gè)去重的邏輯分別抽象成樹(shù)形結(jié)構(gòu)，大家可以一目了然：為什么兩種寫(xiě)法都可以以及哪一種效率更高!

是不是豁然開(kāi)朗了!!

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。


標(biāo)題名稱(chēng)：排列問(wèn)題也要去重了！
標(biāo)題URL：http://www.5511xx.com/article/dphipij.html