[LeetCode] 47. Permutations II 全排列之二

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

這道題是之前那道 Permutations 的延伸，由于輸入數(shù)組有可能出現(xiàn)重復數(shù)字，如果按照之前的算法運算，會有重復排列產生，我們要避免重復的產生，在遞歸函數(shù)中要判斷前面一個數(shù)和當前的數(shù)是否相等，如果相等，且其對應的 visited 中的值為1，當前的數(shù)字才能使用（下文中會解釋這樣做的原因），否則需要跳過，這樣就不會產生重復排列了，代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> out, visited(nums.size(), 0);
        sort(nums.begin(), nums.end());
        permuteUniqueDFS(nums, 0, visited, out, res);
        return res;
    }
    void permuteUniqueDFS(vector<int>& nums, int level, vector<int>& visited, vector<int>& out, vector<vector<int>>& res) {
        if (level >= nums.size()) {res.push_back(out); return;}
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i] == 1) continue;
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue;
            visited[i] = 1;
            out.push_back(nums[i]);
            permuteUniqueDFS(nums, level + 1, visited, out, res);
            out.pop_back();
            visited[i] = 0;
        }
    }
};

在使用上面的方法的時候，一定要能弄清楚遞歸函數(shù)的 for 循環(huán)中兩個 if 的剪枝的意思。在此之前，要弄清楚 level 的含義，這里用數(shù)組 out 來拼排列結果，level就是當前已經拼成的個數(shù)，其實就是 out 數(shù)組的長度。我們看到，for 循環(huán)的起始是從0開始的，而本題的解法二，三，四都是用了一個 start 變量，從而 for 循環(huán)都是從 start 開始，一定要分清楚 start 和本解法中的 level 的區(qū)別。由于遞歸的 for 都是從0開始，難免會重復遍歷到數(shù)字，而全排列不能重復使用數(shù)字，意思是每個 nums 中的數(shù)字在全排列中只能使用一次（當然這并不妨礙 nums 中存在重復數(shù)字）。不能重復使用數(shù)字就靠 visited 數(shù)組來保證，這就是第一個 if 剪枝的意義所在。關鍵來看第二個 if 剪枝的意義，這里說當前數(shù)字和前一個數(shù)字相同，且前一個數(shù)字的 visited 值為0的時候，必須跳過。這里的前一個數(shù) visited 值為0，并不代表前一個數(shù)字沒有被處理過，也可能是遞歸結束后恢復狀態(tài)時將 visited 值重置為0了，實際上就是這種情況，下面打印了一些中間過程的變量值，如下所示：

注意看這里面的 skipped 1 表示的是第一個 if 剪枝起作用的地方，skipped 2 表示的是第二個 if 剪枝起作用的地方。我們主要關心的是第二個 if 剪枝，看上方第一個藍色標記的那行，再上面的紅色一行表示在 level = 1, i = 1 時遞歸調用結束后，恢復到起始狀態(tài)，那么此時 out 數(shù)組中只有一個1，后面的2已經被 pop_back() 了，當然對應的 visited 值也重置為0了，這種情況下需要剪枝，當然不能再一次把2往里加，因為這種情況在遞歸中已經加入到結果 res 中了，所以到了 level = 1, i = 2 的狀態(tài)時，nums[i] == nums[i-1] && visited[i-1] == 0 的條件滿足了，剪枝就起作用了，這種重復的情況就被剪掉了。

還有一種比較簡便的方法，在 Permutations 的基礎上稍加修改，用 TreeSet 來保存結果，利用其不會有重復項的特點，然后在遞歸函數(shù)中 swap 的地方，判斷如果i和 start 不相同，但是 nums[i] 和 nums[start] 相同的情況下跳過，繼續(xù)下一個循環(huán)，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        set<vector<int>> res;
        permute(nums, 0, res);
        return vector<vector<int>> (res.begin(), res.end());
    }
    void permute(vector<int>& nums, int start, set<vector<int>>& res) {
        if (start >= nums.size()) res.insert(nums);
        for (int i = start; i < nums.size(); ++i) {
            if (i != start && nums[i] == nums[start]) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
            swap(nums[i], nums[start]);
        }
    }
};

對于上面的解法，你可能會有疑問，我們不是在 swap 操作之前已經做了剪枝了么，為什么還是會有重復出現(xiàn)，以至于還要用 TreeSet 來取出重復呢?？偢杏X使用 TreeSet 去重復有點耍賴，可能并沒有探究到本題深層次的內容。這是很好的想法，首先嘗試將上面的 TreeSet 還原為 vector，并且在主函數(shù)調用遞歸之前給 nums 排個序（代碼參見評論區(qū)三樓），然后測試一個最簡單的例子：[1, 2, 2]，得到的結果為：

[[1,2,2], [2,1,2], [2,2,1], [2,2,1],  [2,1,2]]

我們發(fā)現(xiàn)有重復項，那么剪枝究竟在做些什么，怎么還是沒法防止重復項的產生！那個剪枝只是為了防止當 start = 1, i = 2 時，將兩個2交換，這樣可以防止 {1, 2, 2} 被加入兩次。但是沒法防止其他的重復情況，要鬧清楚為啥，需要仔細分析一些中間過程，下面打印了一些中間過程的變量：

問題出在了遞歸調用之后的還原狀態(tài)，參見上面的紅色的兩行，當 start = 0, i = 2 時，nums 已經還原到了 {1, 2, 2} 的狀態(tài)，此時 nums[start] 不等于 nums[i]，剪枝在這已經失效了，那么交換后的 {2, 2, 1} 還會被存到結果 res 中，而這個狀態(tài)在之前就已經存過了一次。

注意到當 start = 0, i = 1 時，nums 交換之后變成了 {2, 1, 2}，如果能保持這個狀態(tài)，那么當 start = 0, i = 2 時，此時 nums[start] 就等于 nums[i] 了，剪枝操作就可以發(fā)揮作用了。怎么才能當遞歸結束后，不還原成為交換之前的狀態(tài)的呢？答案就是不進行還原，這樣還是能保存為之前交換后的狀態(tài)。只是將最后一句 swap(nums[i], nums[start]) 刪掉是不行的，因為遞歸函數(shù)的參數(shù) nums 是加了&號，就表示引用了，那么之前調用遞歸函數(shù)之前的 nums 在遞歸函數(shù)中會被修改，可能還是無法得到我們想要的順序，所以要把遞歸函數(shù)的 nums 參數(shù)的&號也同時去掉才行，參見代碼如下：

解法三：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        permute(nums, 0, res);
        return res;
    }
    void permute(vector<int> nums, int start, vector<vector<int>>& res) {
        if (start >= nums.size()) res.push_back(nums);
        for (int i = start; i < nums.size(); ++i) {
            if (i != start && nums[i] == nums[start]) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
        }
    }
};

好，再測試下 [1, 2, 2] 這個例子，并且把中間變量打印出來：

明顯發(fā)現(xiàn)短了許多，說明剪枝發(fā)揮了作用，看上面紅色部分，當 start = 0, i = 1 時，遞歸函數(shù)調用完了之后，nums 數(shù)組保持了 {2, 1, 2} 的狀態(tài)，那么到 start = 0, i = 2 的時候，nums[start] 就等于 nums[i] 了，剪枝操作就可以發(fā)揮作用了。

這時候你可能會想，調用完遞歸不恢復狀態(tài)，感覺怪怪的，跟哥的遞歸模版不一樣啊，容易搞混啊，而且一會加&號，一會不加的，這尼瑪誰能分得清啊。別擔心，I gotcha covered! 好，既然還是要恢復狀態(tài)的話，就只能從剪枝入手了，原來那種 naive 的剪枝方法肯定無法使用，矛盾的焦點還是在于，當 start = 0, i = 2 時，nums 被還原成了 start = 0, i = 1 的交換前的狀態(tài) {1, 2, 2}，這個狀態(tài)已經被處理過了，再去處理一定會產生重復，怎么才知道這被處理過了呢，當前的 i = 2，需要往前去找是否有重復出現(xiàn)，由于數(shù)組已經排序過了，如果有重復，那么前面數(shù)一定和當前的相同，所以用一個 while 循環(huán)，往前找和 nums[i] 相同的數(shù)字，找到了就停下，當然如果小于 start 了也要停下，那么如果沒有重復數(shù)字的話，j 一定是等于 start-1 的，那么如果不等于的話，就直接跳過就可以了，這樣就可以去掉所有的重復啦，參見代碼如下：

解法四：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        permute(nums, 0, res);
        return res;
    }
    void permute(vector<int>& nums, int start, vector<vector<int>>& res) {
        if (start >= nums.size()) res.push_back(nums);
        for (int i = start; i < nums.size(); ++i) {
            int j = i - 1;
            while (j >= start && nums[j] != nums[i]) --j;
            if (j != start - 1) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
            swap(nums[i], nums[start]);
        }
    }
};

同樣，我們再測試下 [1, 2, 2] 這個例子，并且把中間變量打印出來：

到 start = 0, i = 2 的時候，j 此時等于1了，明顯不是 start-1，說明有重復了，直接 skip 掉，這樣剪枝操作就可以發(fā)揮作用了。

之前的 Permutations 中的解法三也可以用在這里，只不過需要借助 TreeSet 來去重復，博主還未想出其他不用集合的去重復的方法，哪位看官大神們知道的話，請一定要留言告知博主，參見代碼如下：

解法五：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if (nums.empty()) return vector<vector<int>>(1, vector<int>());
        set<vector<int>> res;
        int first = nums[0];
        nums.erase(nums.begin());
        vector<vector<int>> words = permuteUnique(nums);
        for (auto &a : words) {
            for (int i = 0; i <= a.size(); ++i) {
                a.insert(a.begin() + i, first);
                res.insert(a);
                a.erase(a.begin() + i);
            }
        }   
        return vector<vector<int>> (res.begin(), res.end());
    }
};

之前的 Permutations 中的解法四博主沒法成功修改使其可以通過這道題，即便是將結果 res 用 TreeSet 來去重復，還是不對。同樣，哪位看官大神們知道的話，請一定要留言告知博主。后經過微信公眾號上的熱心網友 hahaboy 的提醒下，可以通過加上一個剪枝從而通過這道題，在最中間的 for 循環(huán)的最后，判斷若 num 等于 t[i]，直接 break 掉當前循環(huán)，否則會產生重復項，參見代碼如下：

解法六：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res{{}};
        for (int num : nums) {
            for (int k = res.size(); k > 0; --k) {
                vector<int> t = res.front();
                res.erase(res.begin());
                for (int i = 0; i <= t.size(); ++i) {
                    vector<int> one = t;
                    one.insert(one.begin() + i, num);
                    res.push_back(one);
                    if (i < t.size() && num == t[i]) break;
                }
            }
        }
        return res;
    }
};

之前的 Permutations 中的解法五卻可以原封不動的搬到這道題來，看來自帶的 next_permutation() 函數(shù)就是叼啊，自帶去重復功能，叼叼叼！參見代碼如下：

解法七：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        res.push_back(nums);
        while (next_permutation(nums.begin(), nums.end())) {
            res.push_back(nums);
        }
        return res;
    }
};

到此這篇關于C++實現(xiàn)LeetCode(47.全排列之二)的文章就介紹到這了,更多相關C++實現(xiàn)全排列之二內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論