Leetcode: Permutations II

本文主要是介绍Leetcode: Permutations II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
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;}
};

这篇关于Leetcode: Permutations II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---