LeetCode

2013.12.15 05:30

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].

Solution:

　　This time the array may contain duplicates, so I implemented the next_permutation() myself, and called it until all the permutations are traversed.

　　You can see the two problems here and find their connection with this problem: Next Permutation and Permutations.

　　Time complexity is O(n * n! / (a! * b! * c! * ...)), where a, b, c, ... are the number of groups of duplictate elements. Space complexity is O(n).

Accepted code:

 1 // 1CE, 2MLE, 1AC, not so easy
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     vector<vector<int> > permuteUnique(vector<int> &num) {
 8         // IMPORTANT: Please reset any member data you declared, as
 9         // the same Solution instance will be reused for each test case.
10         int i, j;
11         int n;
12         
13         n = result.size();
14         for(i = 0; i < n; ++i){
15             result[i].clear();
16         }
17         result.clear();
18         
19         sort(num.begin(), num.end());
20         n = num.size();
21         if(n <= 0){
22             return result;
23         }
24         while(true){
25             result.push_back(num);
26             for(i = n - 1; i > 0; --i){
27                 if(num[i - 1] < num[i]){
28                     break;
29                 }
30             }
31             if(i <= 0){
32                 break;
33             }
34             --i;
35             for(j = n - 1; j > i; --j){
36                 if(num[j] > num[i]){
37                     break;
38                 }
39             }
40             myswap(num[j], num[i]);
41             // 2MLE here, reverse(i + 1, n - 1), not reverse(i, n - 1);
42             reverse(num, i + 1, n - 1);
43         }
44         
45         return result;
46     }
47 private:
48     vector<vector<int>> result;
49     void myswap(int &x, int &y) {
50         int tmp;
51         
52         tmp = x;
53         x = y;
54         y = tmp;
55     }
56     
57     void reverse(vector<int> &num, int left, int right) {
58         int i;
59         
60         if(left > right){
61             reverse(num, right, left);
62             return;
63         }
64         
65         i = left;
66         // 1CE here, how did you submit before even finishing it!!!
67         while(i < left + right - i){
68             myswap(num[i], num[left + right - i]);
69             ++i;
70         }
71     }
72 };