Google : Eliminate duplicated bit arrays

Given a binary matrix of N X N of integers ,
you need to return only unique rows of binary arrays
eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
1 1 1 0 1
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0

brute force 需要的时间复杂度是O(n^3), 但是这题有它的特点
如果问题是排序一个只包含0,1的一维数组，那么只要O(n)就可以搞定， 这样就把原数组分裂成了两部分，再递归的分别对两部分排序.... 类似于快排的思想，排序这个矩阵需要O(n^2)的时间复杂度。

好的，排序了以后再遍历这个矩阵，再用O(n^2)的时间复杂度就可以去除重复了：

1. 
   
2. void _inner_sort_bits(bool** pArr, int n, int i, int nDeep);
   
3. 
   
4. bool Equal(bool* p1, bool* p2, int n)
   
5. {
   
6.         assert(p1 && p2 && n > 0);
   
7. 
   
8.         for (int i = 0; i < n; i++)
   
9.         {
   
10.                 if (p1[i] != p2[i])
    
11.                         return false;
    
12.         }
    
13. 
    
14.         return true;
    
15. }
    
16. 
    
17. void PrintBitArray(bool* p, int n)
    
18. {
    
19.         assert(p && n > 0);
    
20. 
    
21.         for (int i = 0; i < n; i++)
    
22.         {
    
23.                 if (p[i])
    
24.                         cout<<1<<" ";
    
25.                 else
    
26.                         cout<<0<<" ";
    
27.         }
    
28. 
    
29.         cout<<endl;
    
30. }
    
31. 
    
32. void SortBitMatrix(bool** pArr, int n)
    
33. {
    
34.         assert(pArr && n > 0);
    
35. 
    
36.         _inner_sort_bits(pArr, n, 0, n);
    
37. }
    

复制代码