LeetCode 47 全排列II(有重复元素 dfs)
2021/11/12 23:15:22
本文主要是介绍LeetCode 47 全排列II(有重复元素 dfs),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
对于有重复数字的全排列,分析重复情况的主要来源:相同的位置选择了不同但数值相同的数字。
对于重复的数字,人为控制放入相同数字的数量(枚举从1~N),只要保证选择i
个连续相同数字后,紧跟的数字不相同(不能构成连续的i+1
个相同数字)即可保证排列唯一性。
tricks:用map存储每个数字的个数。枚举for循环结束后,统一pop出N个相同数字维护当前排列。
附上代码:
class Solution { map<int,int> vis; public: void dfs(vector<int>& nums, vector<vector<int>>& out, vector<int>& curr){ if(curr.size() >= nums.size()) { out.push_back(curr); return; } for(map<int,int>::iterator it = vis.begin(); it != vis.end(); it++){ if(curr.size() > 0 && curr.back() == it->first) continue; int temp = it->second; while(it->second > 0) { vis[it->first]--; curr.push_back(it->first); dfs(nums, out, curr); } vis[it->first] = temp; while(temp > 0){ curr.pop_back(); temp--; } } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> out; vector<int> current; sort(nums.begin(), nums.end()); for(auto n:nums){ if(vis.count(n) == 0) vis[n] = 1; else vis[n]++; } dfs(nums, out, current); return out; } };
这篇关于LeetCode 47 全排列II(有重复元素 dfs)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享