1072.md

title	description	keywords
1072. 按列翻转得到最大值等行数	LeetCode 1072. 按列翻转得到最大值等行数题解，Flip Columns For Maximum Number of Equal Rows，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1072. 按列翻转得到最大值等行数 按列翻转得到最大值等行数 Flip Columns For Maximum Number of Equal Rows 解题思路 数组 哈希表 矩阵

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

🟠 Medium  🔖  数组 哈希表 矩阵  🔗 力扣 LeetCode

题目

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.

题目大意

给定 m x n 矩阵 matrix 。

你可以从中选出任意数量的列并翻转其上的 每个单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）

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

示例 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

解题思路

翻转某些列实际上可以看作对每一行进行某个数字 K 的按位异或操作，以将其转换为某种标准形式（全 0 或全 1）。

我们可以将每一行看做一个二进制数字 X，希望找到一组翻转，使得行 X 的结果满足 X ^ K 等于全 0 或全 1。也就是说，要找到那些在翻转后可以变成相同模式（全 0 或全 1）的行。

例如，如果 K = 1，则计算行 X = (00000...001，或 1111....110)。

1. 行模式的标准化

• 两行相等的条件是：一行的每一位与另一行的每一位要么完全相同，要么完全相反。
• 对于每一行，将其标准化为一种唯一的形式：
  • 如果该行的首位为 1，则将其整体取反，使首位为 0；
  • 否则保持原样。
• 这样，所有可以通过列翻转变成一致的行都会映射到同一个模式。

2. 使用哈希表统计模式频率

• 使用一个哈希表 count 记录每种模式出现的次数。
• 遍历矩阵中的每一行，计算其标准化模式，将模式作为键存入哈希表。

3. 最后返回哈希表中最大频率对应的值。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 是行数，n 是列数。
  • 遍历矩阵中的每一行和每一列，时间复杂度为 O(m * n)；
  • 计算模式和更新哈希表的操作为 O(m * n)。
• 空间复杂度：O(m * n)，需要一个哈希表存储模式及其频率，极端情况下每一行模式都不同。

代码

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var maxEqualRowsAfterFlips = function (matrix) {
	const m = matrix.length,
		n = matrix[0].length;
	let count = new Map();
	// 遍历每一行
	for (let row of matrix) {
		// 标准化模式
		const key = row.map((bit) => (row[0] ? 1 - bit : bit)).join('');
		count.set(key, (count.get(key) || 0) + 1);
	}
	return Math.max(...count.values());
};