翻转列以获得最大相等行数

1072。翻转列以获得最大数量的相等行

难度：中等

主题：数组、哈希表、矩阵

给你一个 m x n 二进制矩阵。

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

返回经过一定次数的翻转后所有值都相等的最大行数.

示例1：

• 输入： 矩阵 = [[0,1],[1,1]]
• 输出： 1
• 解释：翻转没有值后，1 行所有值都相等。

示例2：

• 输入： 矩阵 = [[0,1],[1,0]]
• 输出： 2
• 解释：翻转第一列中的值后，两行的值相等。

示例 3：

• 输入： 矩阵 = [[0,0,0],[0,0,1],[1,1,0]]
• 输出： 2
• 说明：翻转前两列的值后，最后两行的值相等。

约束：

• m == 矩阵.length
• n == 矩阵[i].length
• 1
• 矩阵[i][j]为0或1。

提示：

1. 翻转列的子集就像对每行执行某个数字 K 的按位异或运算。我们想要 X 行 X ^ K = 全 0 或全 1。这与 X = X^K ^K = (全 0 或全 1) ^ K 相同，因此我们要计算设置了相反位的行。例如，如果 K = 1，则我们计算行数 X = (00000...001，或 1111....110)。

解决方案：

我们可以利用哈希映射对可以通过翻转某些列使其相同的行进行分组。可以变得相同的行具有相同的模式或互补的模式（按位否定）。

以下是分步解决方案：

算法：

1. 对于每一行，计算其模式和互补模式：
   • 图案就是行本身。
   • 互补模式是翻转行中所有位的结果。
2. 使用哈希映射来计算模式及其补集的出现次数。
3. 任何单个模式或其补集的最大计数给出结果。

让我们用 PHP 实现这个解决方案：1072。翻转列以获得最大数量的相等行

<?php /**
 * @param Integer[][] $matrix
 * @return Integer
 */
function maxEqualRowsAfterFlips($matrix) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$matrix1 = [[0, 1], [1, 1]];
$matrix2 = [[0, 1], [1, 0]];
$matrix3 = [[0, 0, 0], [0, 0, 1], [1, 1, 0]];

echo maxEqualRowsAfterFlips($matrix1) . "\n"; // Output: 1
echo maxEqualRowsAfterFlips($matrix2) . "\n"; // Output: 2
echo maxEqualRowsAfterFlips($matrix3) . "\n"; // Output: 2
?>

解释：

1. 模式和补语：
   • 对于每一行，模式是连接的行（例如，010）。
   • 补码翻转该行的所有位（例如 101）。
2. 哈希映射：计算每个模式及其补集的出现次数。这有助于对可以相同的行进行分组。
3. 最大计数： 查找单个模式或其补集的最大计数，以确定可以使多少行相同。

复杂：

• 时间复杂度： O(m x n)，其中 m 是行数，n 是列数。
• 空间复杂度： O(m x n)，用于在哈希映射中存储模式。

该解决方案遵守约束条件，并且对于问题规模而言非常有效。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是翻转列以获得最大相等行数的详细内容。更多信息请关注PHP中文网其他相关文章！