解题思路:
1.获取信息:
给定一个可包含重复数字的序列,按任意顺序返回所有不重复的全排列
提示信息:1 <= nums.length <= 8
-10 <= nums[i] <= 10
2.分析题目:
相较于46题,它多限制了一个条件,也就是数组中可能出现重复的数字了
所以说它是46题的进阶版
对于出现重复数字,我们可以将46题中的查重容器变换一下,改为存储整型的数组,这样就可以针对于某个数字记录下它出现了几次
不止是上面的变动,这道题因为数组中会出现重复的数字,所以重复率相较于46题变高了
那么重复率为什么会变高呢?
因为原本在某个位置取了一个数,在走它其他的支线时,因为会出现重复的数,就会再次取到相同的数,那么后续的支线也就相同了,我给个例子解释
例如[ 1, 1, 2 ]
我们遍历数组取出每个数作为每种排列的第一个数
那么第一个位置上就会出现两次1,后续再取第二个数,第三个数,那这两次都是相同的
所以就需要再次添加一个查重的操作
3.示例查验:略
4.尝试编写代码:
(1)暴力法:
思路:与46题的思想基本一致,只不过多加了一次查重的操作,并且将原有的查重操作进阶了一下,具体看代码吧
你可以结合46题的代码来看,我究竟新添加了哪些步骤,可以帮助你更好地理解
class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>>res;vector<int>tab(21,0);//原有的查重操作进阶版for(int i=0;i<nums.size();i++)tab[nums[i]+10]++;vector<int>path;GetRes(res,tab,path,nums);return res;}
private:void GetRes(vector<vector<int>>&res,vector<int>&tab,vector<int>&path,vector<int>&nums){if(path.size()==nums.size()){res.push_back(path);return;}vector<bool>In(21,true);//新添加的查重操作for(int i=0;i<nums.size();i++){if(In[nums[i]+10]&&tab[nums[i]+10]){In[nums[i]+10]=false;tab[nums[i]+10]--;path.push_back(nums[i]);GetRes(res,tab,path,nums);path.pop_back();tab[nums[i]+10]++;}}}
};
今天的题解就到这里了,四川真的好热,看着外面的太阳,我就感觉好害怕,闲来没事就把今天的题解解决了,大大的进步
现在要玩一下英雄联盟了,奖励一下自己