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

🟠   🔖  数组 哈希表 矩阵  🔗 力扣 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());
};