LeetCode47， 全排列進階，如果有重複元素怎麼辦？

今天是LeetCode第28篇，依然是全排列的問題。

如果對全排列不熟悉或者是最近關注的同學可以看一下上一篇文章：

LeetCode就是喜歡這樣，把類似的問題放在一起，讓你刷的時候一起刷，從而更加深刻地理解。今天的問題同樣是全排列，不過稍稍不同的是，我們有一個限制條件不一樣，給定的元素當中可能存在重複。但是元素存在重複，我們並不想最後的結果也出現重複，這個時候應該怎麼辦？

舉個例子，比如我們有一個排列是[1, 2, 2].

它的所有排列是[1, 2, 2], [2, 1, 2], [2, 2, 1]，但是注意，在之前的做法當中，我們把所有的元素看成是unique的，但是現在這個條件被破壞了。顯然我們需要在實現全排列的基礎上解決這個問題。

無腦解決

解決的方法有兩種，第一種是無腦解決。是的你沒有看錯，因為我們分析一下就會發現next_permutation循環的方法在這題當中仍然奏效，原因也很簡單，因為我們每次用next_permutation求得字典序+1的下一個排列的時候，顯然已經去除了重複元素的情況。為什麼？因為同樣元素換位置字典序是不會變化的。

比如下圖當中，我們更換兩個2的順序，整個序列的字典序是沒有變化的，要使得字典序變化一定要交換不同的元素。所以這個解法是可行的。

next_permutation是返回當前序列字典序+1的序列的算法，這個算法在之前的文章當中出現過，所以我就不贅述它的原理了，如果你不記得或者是忘記了的話，可以點擊下方的鏈接回顧一下：

這個解法和上一題的最後一個解法完全一樣，連改動都不需要，我們直接把代碼copy過來把函數名匹配上就可以提交了。這也是我說這道題無腦的原因。

回溯法

顯然重複之前的工作並不能讓我們變得更強，所以我們還是要回到正解上來。在之前的文章我們知道，生成全排列的通常做法是使用回溯法。那麼如果使用回溯法我們怎麼解決重複元素的問題呢？

還是老慣例，我們要解決問題，首先來分析問題，我們知道重複的元素會干擾全排列生成的算法，那麼它為什麼會干擾，是怎麼幹擾的？

在回溯法當中，我們是順序遍歷位置，然後枚舉放置的元素。於是我們大概可以想出兩種可能導致重複的情況。

我們先來看情況1，情況1很簡單，就是

第二種情況也比較容易想明白，還是同樣的例子，我們給數組當中的兩個4編號，一個編號是4_1，一個是4_2，我們會發現對於兩個位置，我們

表面上來看情況是這兩種，但是如果深入分析會發現這兩種情況其實說的是一回事，結果出現重複都是由於全排列的時候元素出現不穩定造成的。

這裡的“

同樣，如果我們能保證執行全排列的時候元素的穩定性，那麼這個問題就解決了。表面上看這似乎是一個優化問題，其實不然，考察的是穩定性這個概念。

如果能想到穩定性這點，離解決已經很近了。我們要保證穩定性，也就是說對於當前元素，我們需要保證前面的同元素已經放置了，那麼在一個排列中，相同元素的擺放位置應該是遞增的。我們用map記錄每一個元素最後一次擺放的位置，控制它在往下遞歸的過程當中遞增即可。

比如當數組當中有兩個4的時候，第一個4如果還沒有擺放，那麼第二個4也不能擺。但是由於我們在判斷要不要擺放第二個4的時候，並不知道前面是否還有其他的4，所以我們只能倒過來，判斷在擺放第一個4的時候，是不是已經放過了後面的4，如果是的話，那麼這個操作不能執行。用語言描述這個邏輯有點繞，我們來看下圖就明白了：

我們擺放了第一個4之後，map[4] = 4，記錄的是擺放的4的下標，當我們枚舉放置第一個4的時候，發現已經放置的4下標大於當前，說明非法，放置了會引起重複。

還有一個問題是當我們回溯的時候，需要重置map裡的值，比如：

在一次遞歸當中，我們放置了兩個4，放了第二個4之後，map[4] = 4，當我們回溯彈出第二個4的時候，這個時候的map[4]應該是多少？

答案不難，應該是1，也就是第一個4的下標。所以我們在遞歸的時候，在更新map之前，需要記錄一下之前的值，方便回溯的時候恢復。

我們整理一下，思路可以得到代碼：

改進

上面這個方法其實有點複雜，理解起來有很多細節，一個比較蛋疼的點就是我們用了map去記錄了位置，由於要更新map，所以還需要記錄之前的值，還需要判斷元素不在map當中的情況。並且map的查找存在開銷，那麼我們能不能不用map呢？

在想怎麼不用map的替代方案之前，我們需要先搞清楚，我們為什麼要使用map？

這個問題問的並不是一個充分問題，而是一個必要問題，不是用map解決了什麼問題，而是我們為什麼只能用map不可呢？

因為map是一個容器，它能存儲數據。對於一個元素t來說，我們並不知道它在數組nums當中之前出現的位置是哪裡，我們也並不知道這些之前出現的t有沒有被放入當前的排列裡。我們用map記錄下t的下標，本質原因是這個。map只是我們實現這個功能的手段，不是目的。

所以我們如果不想使用map，必須要保證能夠知道每一個元素的擺放位置才可以。要做到這點其實並不難，我們只需要對nums排序就好了。排序之後，所有相同的元素都會挨在一起。那麼，對於位置p來說，我們只需要判斷如果nums[p-1] 等於 nums[p]的話，必須要flag[p-1]等於true，也就是說對於元素v來說，它前面一位如果是v必須要放置好，才能放置當前的v，否則就是非法的。這樣每一個v都限制前一個v，就保證了所有的v不會起衝突。這是一種鏈式限制的思想。

通過這種方法，我們就可以拋棄掉map的使用，進而極大地提升效率。

想清楚了原理之後，代碼非常簡單：

你看，我們只需要排序，也不需要引入新的數據結構，就可以完美地解決這個問題。其實很多時候，解決問題的途徑有很多種，能不能想到更好的解法除了取決於能力之外，更重要的還是對問題的理解。

這道題也是一個Medium的問題，總體來說難度並不大。如果可以不看標程，獨立通過這道題，就說明對全排列這個問題的思考已經比較到位了。

今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。

閱讀更多 承志的算法課堂 的文章

關鍵字: 算法 舉個 進階