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].
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 |
class
Solution {public: vector<vector<int> > re; vector<vector<int> > permuteUnique(vector<int> &num) { map<int
, int> m; int
size = num.size(); vector <int> result; for(int
i = 0; i < size ;i++) { m[num[i]]++; } per(result,0,0,m,size); return
re; } void
per(vector<int> now ,int
flag, int
put,map<int
, int> m,int
size) { if(flag == 1) { now.push_back(put); m[put]--; if(now.size() == size) { re.push_back(now); return; } } else
flag =1; for(map<int
,int>::iterator iter = m.begin();iter !=m.end() ;iter++) { if(iter->second > 0) { per(now ,1, iter->first,m,size); } } }}; |
用dfs应该会更快。但是用dfs需要先排一下序。 n log n，之后用n^2进行取元素。
我用map思路相似，但是每次取元素都需要加一个
Permutations II,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3620717.html