三种解法解含重复数字的全排列

LeetCode 47 全排列II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii

解法一

每次让一个数字做为首数字，剩下的递归排列。通过swap来改变首数字。
依次将待排列的集合规模变小，若某一个数字做过首字符则跳过。

如 1 2 2 3
先让1做第一个数字， 剩下子序列2 2 3进行递归
对2 2 3进行排列
可得 1 2 2 3、1 2 3 2 、1 3 2 2
当st=1,i=2时 nums[st]=2,nums[st]=2 此时进入isSwap函数判断，st=1,end=i=2,再nums[st]~nums[end-1]中出现了nums[end]的数字，说明nums[end]已经在st、st+1…,end-1位置中出现过，无需重复排列，所以continue。

class Solution {
public:void swap(int &a,int &b){int tmp=a;a=b;b=tmp;}bool isSwap(vector<int>& nums,int st,int end){for(int i=st;i<end;i++){if(nums[i]==nums[end]){return false;}}return true;}void  curusion(int st,vector<int>& nums,int numsSize,vector<vector<int>>& res,vector<int> & tmp){if(st==numsSize){for(int i=0;i<numsSize;i++){tmp.push_back(nums[i]);}res.push_back(tmp);tmp.clear();return;}for(int i=st;i<numsSize;i++){if(!isSwap(nums,st,i))continue;swap(nums[i],nums[st]);curusion(st+1,nums,numsSize,res,tmp);swap(nums[i],nums[st]);}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;vector<int> tmp;curusion(0,nums,nums.size(),res,tmp);return res;}};

提交结果：

解法二 用map映射

一开始想用一个数组去标记某个数是否已经在某个位置上出现过，但由于可能出现负数问题，只能利用map进行标记。

class Solution {
public:void swap(int &a,int &b){int tmp=a;a=b;b=tmp;}void  curusion(int st,vector<int>& nums,int numsSize,vector<vector<int>>& res,vector<int> & tmp){if(st==numsSize){for(int i=0;i<numsSize;i++){tmp.push_back(nums[i]);}res.push_back(tmp);tmp.clear();return;}map<int,int>mp;for(auto e:nums){mp[e]=0;}  for(int i=st;i<numsSize;i++){if(mp[nums[i]]==1)continue;mp[nums[i]]=1;swap(nums[i],nums[st]);curusion(st+1,nums,numsSize,res,tmp);swap(nums[i],nums[st]);}//一整个for循环是nums[st]~nums[numsSize-1]的序列中进行排列，对一个子序列排列使用一个map映射，并且每一个子序列开始排序前要清零}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;vector<int> tmp;curusion(0,nums,nums.size(),res,tmp);return res;}};

提交结果如下：

解法三

在leetcode题解中学到用从map中选数字排列，每次从map中选未使用过的非重复数字或者未全部使用完的重复数字。
如 1 2 3 3
初始时 map映射为 [1,1],[2,1],[3,2]
第一个数字从1，2，3中选1 ，递归排列后三个数字，map映射为 [1,0],[2,1],[3,2]
第二个数字从1，2，3中选2，递归排列后两个数字,map映射为[1,0],[2,0],[3,2]
第三个数字从1，2，3中选3，递归排列后一个数字，map映射为[1,0],[2,0],[3,1]
第四个数字从1，2，3中选3，map映射为[1,0],[2,0],[3,0],得到一个排列1 2 2 3加入结果集合依次返回上一层,依次恢复mp[3]=1,mp[3]=2,mp[2]=1，返回到第二个数字
第二个数字从1，2，3中选3（遍历2后是3）递归排列第三个数字，map映射为[1,0],[2,1],[3,1]
第三个数字从1，2，3中选2，递归排列第四个数字，map映射为[1,0],[2,0],[3,1]
第四个数字从1，2，3中选3，得到1 3 2 3加入结果集，恢复mp[3]=1,mp[2]=1,返回到排列第三个数字
第三个数字从1，2，3中选3，第四个数字选2 得到1 3 3 2
同理依次得到 2 1 3 3，2 3 1 3，3 1 2 3， 3 2 1 3 ，3 2 3 1，3 3 1 2，3 3 2 1

class Solution {
public:void  curusion(int k,vector<int>& nums,int numsSize,vector<vector<int>>& res,vector<int> & tmp,map<int,int> &mp){if(k==numsSize){res.push_back(tmp);return;}for(auto &p: mp){if(p.second==0) continue;p.second--;tmp.push_back(p.first);curusion(k+1,nums,numsSize,res,tmp,mp);tmp.pop_back();p.second++;}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;vector<int> tmp;map<int,int> mp;for(int e:nums){mp[e]++;}curusion(0,nums,nums.size(),res,tmp,mp);return res;}
};  

提交结果如下

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！