更新时间:2022-08-12 18:53:17
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]46.Permutations非常类似,唯一的区别就是在这个题目中元素集合可以出现重复。这给我们带来一个问题就是如果不对重复元素加以区别,那么类似于{1,1,2}这样的例子我们会有重复结果出现。那么如何避免这种重复呢?方法就是对于重复的元素循环时跳过递归函数的调用,只对第一个未被使用的进行递归,我们那么这一次结果会出现在第一个的递归函数结果中,而后面重复的会被略过。如果第一个重复元素前面的元素还没在当前结果中,那么我们不需要进行递归。想明白了这一点,代码其实很好修改。首先我们要对元素集合排序,从而让重复元素相邻,接下来就是一行代码对于重复元素和前面元素使用情况的判断即可。
/********************************* * 日期:2015-01-19 * 作者:SJF0115 * 题目: 47.Permutations II * 网址:https://oj.leetcode.com/problems/permutations-ii/ * 结果:AC * 来源:LeetCode * 时间复杂度:O(n!) * 空间复杂度:O(n) * 博客: **********************************/ #include <iostream> #include <algorithm> #include <map> #include <vector> using namespace std; class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int> > result; if(num.empty()){ return result; }//if // 排序 sort(num.begin(),num.end()); bool visited[num.size()]; vector<int> visitedVec; // 递归 DFS(num,visited,visitedVec,result); return result; } private: void DFS(vector<int> &num,bool visited[],vector<int> &visitedVec,vector<vector<int> > &result){ // 形成一个全排列 if(num.size() == visitedVec.size()){ result.push_back(visitedVec); return; }//if for(int i = 0;i < num.size();++i){ // 重复元素 if(i > 0 && !visited[i-1] && num[i] == num[i-1]){ continue; }//if // 如果没有访问过 if(visited[i] == false){ visited[i] = true; visitedVec.push_back(num[i]); DFS(num,visited,visitedVec,result); visitedVec.pop_back(); visited[i] = false; }//if }//for } }; int main(){ Solution solution; vector<int> num; num.push_back(1); num.push_back(1); num.push_back(2); // 重新排列 vector<vector<int> > permutes = solution.permuteUnique(num); // 输出 for(int i = 0;i < permutes.size();i++){ cout<<"["; for(int j = 0;j < permutes[i].size();j++){ cout<<permutes[i][j]; }//for cout<<"]"<<endl; } return 0; }
/********************************* * 日期:2015-01-19 * 作者:SJF0115 * 题目: 47.Permutations II * 网址:https://oj.leetcode.com/problems/permutations-ii/ * 结果:AC * 来源:LeetCode * 时间复杂度:O(n!) * 空间复杂度:O(n) * 博客: **********************************/ #include <iostream> #include <algorithm> #include <map> #include <vector> using namespace std; class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int> > result; if(num.empty()){ return result; }//if int count = num.size(); // 排序 sort(num.begin(),num.end()); // 统计每个元素的个数 map<int,int> countMap; for(int i = 0;i < count;++i){ countMap[num[i]]++; }//for // 每个元素和出现次数复合绑定 vector<pair<int,int> > nums; pair<int,int> pair; for(int i = 0;i < count;++i){ pair.first = num[i]; pair.second = countMap[num[i]]; nums.push_back(pair); }//for vector<int> visited; // 递归 DFS(nums,visited,result); return result; } private: void DFS(vector<pair<int,int> > &nums,vector<int> &visited,vector<vector<int> > &result){ // 形成一个全排列 if(nums.size() == visited.size()){ result.push_back(visited); return; }//if int numCount = nums.size(); for(int i = 0;i < numCount;++i){ int count = 0; // 重复元素不能重复打头 if(i > 0 && nums[i].first == nums[i-1].first){ continue; }//if int countVisit = visited.size(); // 统计重复元素已访问的个数 for(int j = 0;j < countVisit;++j){ if(visited[j] == nums[i].first){ count++; }//if }//for // 如果还有元素没有访问过 if(count < nums[i].second){ visited.push_back(nums[i].first); DFS(nums,visited,result); visited.pop_back(); }//if }//for } }; int main(){ Solution solution; vector<int> num; num.push_back(1); num.push_back(2); num.push_back(1); // 重新排列 vector<vector<int> > permutes = solution.permuteUnique(num); // 输出 for(int i = 0;i < permutes.size();i++){ cout<<"["; for(int j = 0;j < permutes[i].size();j++){ cout<<permutes[i][j]; }//for cout<<"]"<<endl; } return 0; }