乐趣区

关于算法:每日一题按列翻转得到最大值等行数

1072. 按列翻转失去最大值等行数

关键词:哈希表、数组

题目起源:1072. 按列翻转失去最大值等行数 – 力扣(Leetcode)

题目形容

 T 哈希表
 T 数组 

给定 m x n 矩阵 matrix

你能够从中选出任意数量的列并翻转其上的 每个 单元格。(即翻转后,单元格的值从 0 变成 1,或者从 1 变为 0。)

返回 通过一些翻转后,行与行之间所有值都相等的最大行数。

 输出:matrix = [[0,1],[1,1]]
输入:1
解释:不进行翻转,有 1 行所有值都相等。
 输出:matrix = [[0,1],[1,0]]
输入:2
解释:翻转第一列的值之后,这两行都由相等的值组成。
 输出:matrix = [[0,0,0],[0,0,1],[1,1,0]]
输入:2
解释:翻转前两列的值之后,后两行由相等的值组成。

问题剖析

论断:最初由雷同元素形成的行必然雷同或相同。

这个论断显然成立,最初由雷同元素形成的行要么全是 0,要么全是 1。

推论:最初由雷同元素形成的行在最后也是雷同或相同。

这个论断也很好证实,设 a 和 b 为最初由雷同元素组成的两行,若最初 a[i]=b[i],因为每次操作会施加在同一列上,所以,对 a[i] 和 b[i] 施加的操作雷同,所以最后也有 a[i]=b[i];若最初 a[i]!=b[i],也即二者相同,同理,因为对二者施加的操作雷同,所以最后也有 a[i]!=b[i]。

由此,可将最后雷同或相同的行归为一类,于是,可将初始矩阵的行分为若干类,最初由雷同元素形成的行必然属于同一类,且该类只含这些行。故,要求最大行数,等价于求找到含有行数最多的类,该类含有的行数即为最大行数。

因为同一类的行雷同或相同,而属于该类的行要么以 0 结尾要么以 1 结尾,无妨将以 0 结尾的行作为该类的 key,对于以 1 结尾的行,将整行取反便失去其所属类的 key。由上,可失去每行的 key,从而统计出每类含有的行数,最初找到含有最多行数的类所含有的行数。

代码实现

int maxEqualRowsAfterFlips(vector<vector<int>> &matrix) {int n = matrix[0].size();
    unordered_map<string, int> mp;
    for (const auto &row: matrix) {string s(n, '0');
        for (int j = 0; j < n; j++)
            s[j] += row[j] ^ row[0];    // row[0] 为 1 则取反
        mp[s]++;
    }
    // 找到蕴含行数最多的类别蕴含的行数
    int res = 0;
    for (auto &[k, v]: mp)
        res = max(res, v);
    return res;
}

工夫复杂度:O(mn)

空间复杂度:O(m)

退出移动版