LC.P1072[按列翻转得到最大值等行数]

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        int ans = 0, n = matrix[0].length;
        Map<String, Integer> map = new HashMap<>();
        for (int[] row : matrix) {
            char[] s = new char[n];
            for (int i = 0; i < n; ++i) {
                // 将以1开头的行翻转
                s[i] = (char) (row[0] ^ row[i]);
            }
            ans = Math.max(ans, map.merge(String.valueOf(s), 1, Integer::sum));
        }
        return ans;
    }
}
  • 时间复杂度：$O(mn)$，其中$m$为矩阵的行数，$n$为矩阵的列数
  • 空间复杂度：$O(m)$，