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: and .

　　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 
     
       3 using namespace std; 4  5 class Solution { 6 public: 7     vector
      
       
         > permuteUnique(vector
        
          &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
         
          
           > 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
           
             &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 };