首页 > 代码库 > [LeetCode] Permutations II 排列
[LeetCode] Permutations II 排列
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2]
have the following unique permutations:[1,1,2]
, [1,2,1]
, and [2,1,1]
.
Show Tags
Backtracking 这个就是输入一个数组,可能有重复,输出全部的排列。
这题调用stl 就是如下了:
1 #include <vector> 2 #include <iterator> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 7 class Solution { 8 public: 9 vector<vector<int> > permuteUnique(vector<int> &num) {10 int n = num.size();11 vector<vector<int> >ret;12 if(n<1) return ret;13 if(n<2) {ret.push_back(num); return ret; }14 sort(num.begin(),num.end());15 ret.push_back(num);16 while(next_permutation(num.begin(),num.end())){17 ret.push_back(num);18 }19 return ret;20 }21 };22 23 int main()24 {25 vector<int> num = {1,1,2};26 Solution sol;27 vector<vector<int> > ret = sol.permuteUnique(num);28 for(int i=0;i<ret.size();i++){29 copy(ret[i].begin(),ret[i].end(),ostream_iterator<int>(cout," "));30 cout<<endl;31 }32 return 0;33 }
如果不调用嘛,就是自己写一个next_permutation,在Permutations 写过好多个版本了,回顾下stl 的实现逻辑吧:
- 输入数组a[],从右向左遍历,寻找相邻的两个数,使得 left<mid,没找到?就是没有,返回false了。
- 再次从右往左遍历,寻找right >left, 这次的right 不需要一定与left 相连,因为有1 这部,所以有保底的取值(mid)
- 交换left 与right。
- 逆向mid 与其右边。
- 结束。
[LeetCode] Permutations II 排列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。