题目描述

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

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

样例

输入：[[0,1],[1,1]]
输出：1
解释：不进行翻转，有 1 行所有值都相等。

输入：[[0,1],[1,0]]
输出：2
解释：翻转第一列的值之后，这两行都由相等的值组成。

输入：[[0,0,0],[0,0,1],[1,1,0]]
输出：2
解释：翻转前两列的值之后，后两行由相等的值组成。

注意

• 1 <= matrix.length <= 300
• 1 <= matrix[i].length <= 300
• 所有 matrix[i].length 都相等
• matrix[i][j] 为 0 或 1

算法

(暴力枚举) $O(nm)$

1. 直接想这个问题，我们要如何确定翻转哪些列。容易想到，我们翻转的目的，必定可以保证其中一行全是 0（或者 1）。所以我们可以考虑枚举固定每一行，使得这一行全部变成 0 （或者 1），然后统计其他行是否有所有值都相等的。
2. 进一步考虑发现，我们没有必要对固定的那一行真正进行翻转。当某些行的值 完全相等 或 完全相反 时，他们总会同时变为符合条件的行。
3. 基于此，我们直接用哈希表统计，每一种行都有多少个，找到个数最多的即可。

时间复杂度

• 枚举行的时间复杂度为 $O(n)$，加入哈希表和更新答案的时间复杂度为 $O(m)$，故总时间复杂度为 $O(nm)$。

空间复杂度

• 每种行都需要存储进哈希表中，故空间复杂度也为 $O(nm)$。

C++ 代码

class Solution {
public:

    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int ans = 0;

        unordered_map<string, int> r;

        for (int i = 0; i < n; i++) {

            string s;
            for (int j = 0; j < m; j++) {
                s += to_string(matrix[i][0] ^ matrix[i][j]); // 通过判断与行首元素是否相等决定是记录 0（相等）还是 1（不等）。
            }

            r[s]++;
            ans = max(ans, r[s]);
        }

        return ans;
    }
};