Leetcode: Permutations II-蒲公英云

Leetcode: Permutations II

Bertha 。 2022-08-07 15:59 224阅读 0赞

题目：
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], and [2,1,1].

这道题和前面Leetcode: Permutations类似，不过给定序列中有重复的序列。
采用Leetcode: Permutations思路二，不过我们在交换的过程中发现有相同元素出现的时候不进行交换就OK了。

C++参考代码：
（可以对比Leetcode: Permutations思路二的代码，其实两者改动的地方就是啊判断要不要交换）

class Solution
{
private:
    vector<vector<int>> result;
    int size;
    //这个isSwap函数是比原来的Permutation I中新添加的函数
    //该函数用来判断current位置的元素要不要进行交换
    bool isSwap(vector<int> num, int begin, int current)
    {
        for (int i = begin; i < current; ++i)
        {
            if (num[i] == num[current]) return false;
        }
        return true;
    }
    void permuate(vector<int> &num, int index)
    {
        if (index == size)
        {
            result.push_back(num);
            return;
        }
        for (int i = index; i < size; ++i)
        {
            if (i != index && !isSwap(num, index, i)) continue;//这句是新添加的，用来判断如果给定的序列中有重复元素，则跳过重复元素
            swap(num[index], num[i]);//交换i和index元素
            permuate(num, index + 1);//计算除去index元素，后面元素的全排列
            swap(num[index], num[i]);//再换回来
        }
    }
public:
    vector<vector<int> > permuteUnique(vector<int> &num)
    {
        size = int(num.size());
        permuate(num, 0);
        return result;
    }
};