首页 > 代码库 > leetcode 刷题之路 77 Permutations II
leetcode 刷题之路 77 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]
.
Permutations 的升级版,依旧是全排列问题,但是序列中可能会出现重复数字。
思路:采用字典序的非递归方法。从字典顺序最小的一种排列开始,每次获得字典序刚好比前一个排列大的排列,直到得到字典序最大的排列时,就得到了所有的结果,以字符串"abc"为例,"abc"是字典序最小的排列,所有情况按字典序排列为"abc","acb","bac","bca","cba","cab"。
具体步骤为为:
1.字符串进行排序,得到字符串的最小字典序排列(C0C1C2...Cn),Ci<=Ci+1。
2.从后往前,找到一对相邻的升序元素CiCi+1,(Ci<Ci+1),如果遍历完字符串找不到这样的相邻升序对,说明已经达到了字典序最大的全排列
3.从字符串结束位置到位置i遍历,找到比Ci大的元素Cj,交换Cj的位置
4.将Ci+1到Cn所有的字符逆序,这样得到的排列刚好比之前的字典序大(因为转换后Ci+1<Ci+2<...<Cn,为最小字典序)。
5.重复3,4,5过程直到字典序最大。
AC code:
class Solution { public: void swap(int &i,int &j) { int temp=i; i=j; j=temp; } vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int>> res; int i,j,n=num.size(); sort(num.begin(),num.end()); res.push_back(num); while(true) { for(i=n-2;i>=0;i--) if(num[i]<num[i+1]) break; if(i<=-1) return res; for(j=n-1;j>i;j--) if(num[j]>num[i]) break; swap(num[i],num[j]); for(int k=i+1;k<(i+1+n)/2;k++) swap(num[k],num[n-(k-i)]); res.push_back(num); } } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。