1072. Flip Columns For Maximum Number of Equal Rows

Medium

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column. Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

Return the maximum number of rows that have all values equal after some number of flips.

Example 1:

Input: [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

Input: [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

此题似乎没有特别精妙的解法,discuss区排第一的答案看起来就是brute force而已; 复杂度 O(Matrix.height * (Matrix.width + Matrix.height) )

其他的优化也就是用hash进行空间换时间.

 1 class Solution {
 2     public int maxEqualRowsAfterFlips(int[][] matrix) {
 3         int h=matrix.length;
 4         int w=matrix[0].length;
 5         int res=1;
 6         for(int i=0;i<h;++i)
 7         {
 8             int tmp=0;
 9             int []flip=new int[w];
10             for(int j=0;j<w;++j)
11                 flip[j]=1-matrix[i][j]; //flip保存的是第i行 flip后的结果
12             for(int k=0;k<h;++k)
13             {
14                 if(Arrays.equals(matrix[k],matrix[i])||Arrays.equals(matrix[k],flip))   //计算完第j行的flip结果后,把每一行比较,如果等于i或者flip后的结果则命中
15                     ++tmp;
16             }
17             res=Math.max(res,tmp);
18         }
19         return res;
20     }
21 }