首页 > 代码库 > 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]
.
题解:依旧使用的是DFS的思想。
首先需要遍历输入数组,获取一共有多少种不同的数字,每个数字有多少个。 最简单的方法,排序后统计。
然后就是对应位置填数字的游戏了,DFS即可。
1 class Solution { 2 public: 3 vector<vector<int> > vi; 4 vector<int> types; // 数字缓存数组 5 vector<int> counts; // 数字计数器数组 6 vector<int> seq; // 打印数组 7 8 void generatePermute(int len) 9 {10 if(len==0)11 {12 vi.push_back(seq);13 return;14 }15 for(int i=0;i<types.size();i++)16 {17 if((counts[i])>0)18 {19 counts[i]--;20 seq[len-1]=types[i]; //第len-1 是否存放types[i]21 generatePermute(len-1);22 counts[i]++;23 }24 }25 }26 27 vector< vector<int> > permuteUnique(vector<int> &num) {28 29 if(num.size()==0) return vi;30 sort(num.begin(),num.end());31 32 vi.clear(); //结果数组初始化33 types.clear(); //数字缓存数组初始化34 counts.clear(); //计数器初始化35 seq.resize(num.size()); //输出数组大小设定36 37 int j=0;38 types.push_back(num[0]);39 counts.push_back(1);40 41 for(int i=1;i<num.size();i++)42 {43 if(num[i]==types.back())44 {45 counts.back()++;46 }47 else48 {49 types.push_back(num[i]);50 counts.push_back(1);51 }52 }53 generatePermute(num.size());54 return vi;55 }56 };
转载请注明出处: http://www.cnblogs.com/double-win/ 谢谢!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。