Medium

题目描述

给定一个 m x n 的二进制矩阵 matrix。

你可以选择矩阵中任意数量的列并翻转该列中的每个单元格（即，将单元格的值从 0 改为 1，反之亦然）。

返回在经过一些翻转后，具有所有相等值的行的最大数量。

示例 1：

输入：matrix = [[0,1],[1,1]]
输出：1
解释：不翻转任何值，1 行具有所有相等的值。

示例 2：

输入：matrix = [[0,1],[1,0]]
输出：2
解释：翻转第一列的值后，两行都具有相等的值。

示例 3：

输入：matrix = [[0,0,0],[0,0,1],[1,1,0]]
输出：2
解释：翻转前两列的值后，后两行具有相等的值。

约束：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 0 或 1

解题思路

解题思路

关键观察：当我们翻转一些列后，某一行要变成全0或全1，那么另一行如果能同样变成全0或全1，这两行必须满足一个条件：它们要么完全相同，要么完全相反。

具体分析：

  1. 如果两行完全相同，翻转相同的列集合后，它们都会变成相同的结果
  2. 如果两行完全相反，翻转相同的列集合后，一行变成全0，另一行变成全1（或相反）

因此，我们可以将每一行标准化：选择以0开头或以1开头的形式作为"标准形式"。比如：

  • 行 [0,1,0] 的标准形式是 [0,1,0]（已经以0开头）
  • 行 [1,0,1] 的标准形式是 [0,1,0]（翻转所有位得到以0开头）

这样，原本完全相同或完全相反的行都会被映射到同一个标准形式。我们统计每种标准形式出现的次数，最大次数就是答案。

算法步骤：

  1. 遍历每一行，将其转换为标准形式（以0开头）
  2. 使用哈希表统计每种标准形式的出现次数
  3. 返回最大的出现次数

代码实现

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<string, int> count;
        
        for (auto& row : matrix) {
            string pattern = "";
            // 标准化：如果第一个元素是1，则翻转整行
            if (row[0] == 1) {
                for (int val : row) {
                    pattern += to_string(1 - val);
                }
            } else {
                for (int val : row) {
                    pattern += to_string(val);
                }
            }
            count[pattern]++;
        }
        
        int result = 0;
        for (auto& p : count) {
            result = max(result, p.second);
        }
        
        return result;
    }
};

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        count = {}
        
        for row in matrix:
            # 标准化：如果第一个元素是1，则翻转整行
            if row[0] == 1:
                pattern = tuple(1 - x for x in row)
            else:
                pattern = tuple(row)
            
            count[pattern] = count.get(pattern, 0) + 1
        
        return max(count.values())

public class Solution {
    public int MaxEqualRowsAfterFlips(int[][] matrix) {
        var count = new Dictionary<string, int>();
        
        foreach (var row in matrix) {
            string pattern = "";
            // 标准化：如果第一个元素是1，则翻转整行
            if (row[0] == 1) {
                foreach (int val in row) {
                    pattern += (1 - val).ToString();
                }
            } else {
                foreach (int val in row) {
                    pattern += val.ToString();
                }
            }
            
            if (count.ContainsKey(pattern)) {
                count[pattern]++;
            } else {
                count[pattern] = 1;
            }
        }
        
        int result = 0;
        foreach (var kvp in count) {
            result = Math.Max(result, kvp.Value);
        }
        
        return result;
    }
}

var maxEqualRowsAfterFlips = function(matrix) {
    const count = new Map();
    
    for (const row of matrix) {
        let pattern = "";
        // 标准化：如果第一个元素是1，则翻转整行
        if (row[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m × n)
空间复杂度O(m × n)

其中 m 是矩阵的行数，n 是矩阵的列数。时间复杂度主要来自遍历所有元素和字符串操作，空间复杂度主要来自哈希表存储不同的行模式。