Medium!
题目描述:
给定一个可包含重复数字的序列, 返回所有不重复的全排列.
示例:
输入: [1,1,2]
输出:
- [
- [1,1,2],
- [1,2,1],
- [2,1,1]
- ]
解题思路:
这道题是之前那道 Permutations 全排列 http://www.cnblogs.com/grandyang/p/4358848.html 的延伸, 由于输入数组有可能出现重复数字, 如果按照之前的算法运算, 会有重复排列产生, 我们要避免重复的产生, 在递归函数中要判断前面一个数和当前的数是否相等, 如果相等, 前面的数必须已经使用了, 即对应的 visited 中的值为 1, 当前的数字才能使用, 否则需要跳过, 这样就不会产生重复排列了.
C++ 解法一:
- class Solution {
- public:
- vector<vector<int>> permuteUnique(vector<int> &num) {
- vector<vector<int>> res;
- vector<int> out;
- vector<int> visited(num.size(), 0);
- sort(num.begin(), num.end());
- permuteUniqueDFS(num, 0, visited, out, res);
- return res;
- }
- void permuteUniqueDFS(vector<int> &num, int level, vector<int> &visited, vector<int> &out, vector<vector<int>> &res) {
- if (level>= num.size()) res.push_back(out);
- else {
- for (int i = 0; i <num.size(); ++i) {
- if (visited[i] == 0) {
- if (i> 0 && num[i] == num[i - 1] && visited[i - 1] == 0) continue;
- visited[i] = 1;
- out.push_back(num[i]);
- permuteUniqueDFS(num, level + 1, visited, out, res);
- out.pop_back();
- visited[i] = 0;
- }
- }
- }
- }
- };
还有一种比较简便的方法, 在 Permutations http://www.cnblogs.com/grandyang/p/4358848.html 的基础上稍加修改, 我们用 set 来保存结果, 利用其不会有重复项的特点, 然后我们再递归函数中的 swap 的地方, 判断如果 i 和 start 不相同, 但是 nums[i] 和 nums[start] 相同的情况下跳过, 继续下一个循环.
C++ 解法二:
- 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]);
- }
- }
- };
来源: http://www.bubuko.com/infodetail-2632793.html