leetcode 47. 全排列 II---回溯篇6
2023-03-14 22:53:41 时间
全排列 | | 题解集合
引言
注意本题与leetcode 46. 全排列----回溯篇5的区别,区别在于本题所给的可选数组中出现了重复数字,并且要求我们返回所有不重复的全排列
回溯法
思路:
可选数组中出现重复数字,那么为什么重复数字会产生重复的全排列呢?
由图中可以看出,因为出现可选数组出现了两个相邻的数字1,因此,当我们选择第二个数字1时,下面的分支是于第一个数字1完全重复的,因此我们需要进行去重操作。
这里去重思路参考三数之和,先对可选数组进行排序,目的是让重复元素相邻,这里我们可以通过if (i > 0 && nums[i] == nums[i - 1]&&!visited[i-1]) continue;来判断是否有重复元素出现
这里i>0是因为当我们选择第一个数字的时候不需要考虑重复问题,并且当i=0时,nums[i-1]会溢出
这里还需要!visited[i-1]是因为重复问题的出现是因为有重复数字,即当我们将第一个重复数字1的所有排列都遍历一遍后,此时我们来对第二个重复数字1进行遍历会得到与前面一个完全一样的排列,因此这条分支要去掉,并且当我们来对第二个重复数字1进行遍历时,第一个重复数字1是处与没有被选择的状态
其实也就是在leetcode 46. 全排列----回溯篇5加上一个去重的操作,其余的操作于46题全排列完全一致
代码:
class Solution {
vector<vector<int>> ret;
vector<int> num;
vector<bool> visited;
public:
vector<vector<int>> permuteUnique(vector<int>& nums)
{
if (nums.empty()) return ret;
visited.resize(nums.size(), false);
sort(nums.begin(), nums.end());
backTrace(nums);
return ret;
}
void backTrace(vector<int>& nums)
{
if (num.size() == nums.size())
{
ret.push_back(num);
return;
}
for (int i =0; i < nums.size(); i++)
{
if (visited[i]) continue;
// 剪枝条件:i > 0 是为了保证 nums[i - 1] 有意义
//因为选择第一个数字的时候,不需要考虑重复的问题
// 写 !visited[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
if (i > 0 && nums[i] == nums[i - 1]&&!visited[i-1]) continue;
num.push_back(nums[i]);
visited[i] = true;
backTrace(nums);
num.pop_back();
visited[i] = false;
}
}
};
使用set容器去重
思路:
直接dfs全排列然后使用set暴力去重,即我们只需要将46题中用来存储全排列结果的vector替换成set即可
代码:
class Solution {
set<vector<int>> ret;
vector<int> num;
vector<bool> visited;
public:
vector<vector<int>> permuteUnique(vector<int>& nums)
{
if (nums.empty()) return vector<vector<int>>();
visited.resize(nums.size(), false);
backTrace(nums);
return vector<vector<int>>(ret.begin(),ret.end());
}
void backTrace(vector<int>& nums)
{
if (num.size() == nums.size())
{
ret.insert(num);
return;
}
for (int i =0; i < nums.size(); i++)
{
if (visited[i]) continue;
num.push_back(nums[i]);
visited[i] = true;
backTrace(nums);
num.pop_back();
visited[i] = false;
}
}
};
总结
对于由重复数字导致的重复结果去重法,有两种思路:
- 参考三数之和的去重思路,先对数组排序,然后使用相邻数字比较,将重复结果的分支去掉
- 使用set容器去重
相关文章
- 【Docker】Linux安装Docker(极简版)
- [oeasy]python0054_三引号_原样显示字符串_triple_quoted
- TKE集群超级节点pod访问Local模式LoadBalancer类型service不通
- 家庭健康生态全新物种,美的鲜净感空气机颠覆式创新突围空调升级格局
- 智能矿山电子封条监控系统
- PCB板缺陷检测识别系统
- 自定义http服务+中间件案例
- 【ES三周年】在Docker环境下部署EFK日志收集系统
- Typora激活使用教程
- IDEA的配置(一)背景色的配置
- 优思学院|质量人对控制图中的规格线和控制线傻傻分不清?
- 4款Mac解压缩软件,常见且实用
- 苹果发布 2023 款 Mac mini,搭载 M2 和 M2 Pro 芯片
- php manager + mariadb/mysql + iis windows server 配置Discuz X3.5
- 腾讯云windows服务器切换vpc失败的解决方案
- Centos 运维之防火墙篇——①iptables
- Centos 运维之防火墙篇——②firewalld
- Windows系统实例如何导出镜像到本地并成功启动
- 工作玩手机识别监测系统
- 云原生之Docker容器的存储管理