lintcode-16-带重复元素的排列
2024-10-21 18:38:02
带重复元素的排列
给出一个具有重复数字的列表,找出列表所有不同的排列。
样例
给出列表 [1,2,2],不同的排列有:
[
[1,2,2],
[2,1,2],
[2,2,1]
]挑战
使用递归和非递归分别完成该题。
标签
领英 递归 深度优先搜索
code
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int> nums) {
// write your code here
vector<vector<int> > result;
int size = nums.size();
if(size == 0) {
result.push_back(nums);
return result;
}
permute(nums, 0, size, result);
return result;
}
void permute(vector<int> &nums, int begin, int end, vector<vector<int> > &result) {
if(begin == end) {
if(!isExist(nums, result)) {
result.push_back(nums);
}
}
else {
for(int i=begin; i<end; i++) {
int temp = nums[i];
nums[i] = nums[begin];
nums[begin] = temp;
permute(nums, begin+1, end, result);
temp = nums[i];
nums[i] = nums[begin];
nums[begin] = temp;
}
}
}
bool isExist(vector<int> &nums, vector<vector<int> > &result) {
int size = result.size();
if(size == 0)
return false;
for(int i=0; i<size; i++) {
if(isSameNums(nums, result[i])) {
return true;
}
}
return false;
}
bool isSameNums(vector<int> &nums1, vector<int> &nums2) {
int size = nums1.size();
for(int i=0; i<size; i++) {
if(nums1[i] != nums2[i]) {
return false;
}
}
return true;
}
};
最新文章
- 创建多个Oracle数据库及相应的实例
- 微信token验证失败的解决方法
- [bzoj4424]Fairy
- 2,SFDC 管理员篇 - 组织架构
- iOS 并发编程指南
- swun 1184
- Aggressive cows 二分不仅仅是查找
- 关于NRW算法(Quorum算法)
- Bzoj 3343: 教主的魔法 分块,二分
- UNIX基础知识
- Activity之间的跳转
- 触碰jQuery:AJAX异步详解(转)
- Android牛博
- open和fopen的区别:
- MySQL ProxySQL读写分离实践
- arm-none-eabi-gcc编译报错:exit.c:(.text.exit+0x16): undefined reference to `_exit&#39;
- reStructuredText的学习
- 用python 实现一个栈
- 2017-12-21 FriceEngine试用与API中文化
- Android ViewPager + Fragment实现滑动页面