You are given an m x n binary matrix matrix.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).

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

Example 1:

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

Example 2:

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

Example 3:

Input: matrix = [[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.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is either 0 or 1.

按列翻转得到最大值等行数。

给定由若干 0 和 1 组成的矩阵 matrix，从中选出任意数量的列并翻转其上的 每个 单元格。翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。

回经过一些翻转后，行与行之间所有值都相等的最大行数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flip-columns-for-maximum-number-of-equal-rows
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这里我提供一个思路，参考了美版 discussion 的最高票答案。

题目给的是一个只有 0 和 1 的矩阵，问你能否通过翻转任意列 column 里所有的单元格（从 0 变 1 或者从 1 变 0），从而使得经过翻转操作后的矩阵里有尽可能多的行 row 的值是一样的（全是 0 或者全是 1）。假设这样一种情况，如果在经过某次翻转操作后，使得第 i 行都为 0 了，那么我们可以得到如下结论

• 如果此时第 j 行上所有的值也为 0，说明第 j 行在翻转前跟第 i 行应该是一样的
• 如果此时有一个第 k 行上所有的值为1，说明第 k 行在翻转前跟第 i 行应该是恰好相反的

所以这个问题可以转化为找到一个第 i 行使得与这个 row 完全相同的 row 或者完全相反的 row 最多。

具体的做法是我们需要扫描这个二维矩阵，对于当前要扫描的行 row 的所有值我们取反，记为 row2，比如 000110 我们找到 111001，然后去矩阵里找看有多少行是和 row 或者 row2 相同的。

时间O(mn)

空间O(n)

Java实现

 1 class Solution {
 2     public int maxEqualRowsAfterFlips(int[][] matrix) {
 3         int res = 0;
 4         int m = matrix.length;
 5         int n = matrix[0].length;
 6         for (int i = 0; i < m; i++) {
 7             int count = 0;
 8             int[] flip = new int[n];
 9             for (int j = 0; j < n; j++) {
10                 flip[j] = 1 - matrix[i][j];
11             }
12             for (int k = i; k < m; k++) {
13                 if (Arrays.equals(matrix[k], matrix[i]) || Arrays.equals(matrix[k], flip)) {
14                     count++;
15                 }    
16             }
17             res = Math.max(res, count);
18         }
19         return res;
20     }
21 }

 

LeetCode 题目总结