题目描述
给你一个下标从 0 开始、大小为 m x n
的二进制矩阵 matrix
;另给你一个整数 numSelect
,表示你必须从 matrix
中选择的 不同 列的数量。
如果一行中所有的 1
都被你选中的列所覆盖,则认为这一行被 覆盖 了。
形式上,假设 s = {c1, c2, ...., cnumSelect}
是你选择的列的集合。对于矩阵中的某一行 row
,如果满足下述条件,则认为这一行被集合 s
覆盖:
- 对于满足
matrix[row][col] == 1
的每个单元格matrix[row][col]
(0 <= col <= n - 1
),col
均存在于s
中,或者 row
中 不存在 值为1
的单元格。
你需要从矩阵中选出 numSelect
个列,使集合覆盖的行数最大化。
返回一个整数,表示可以由 numSelect
列构成的集合 覆盖 的 最大行数 。
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 12
matrix[i][j]
要么是0
要么是1
1 <= numSelect <= n
样例
示例 1:
输入:matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
输出:3
解释:
图示中显示了一种覆盖 3 行的可行办法。
选择 s = {0, 2} 。
- 第 0 行被覆盖,因为其中没有出现 1 。
- 第 1 行被覆盖,因为值为 1 的两列(即 0 和 2)均存在于 s 中。
- 第 2 行未被覆盖,因为 matrix[2][1] == 1 但是 1 未存在于 s 中。
- 第 3 行被覆盖,因为 matrix[2][2] == 1 且 2 存在于 s 中。
因此,可以覆盖 3 行。
另外 s = {1, 2} 也可以覆盖 3 行,但可以证明无法覆盖更多行。
示例 2:
输入:matrix = [[1],[0]], numSelect = 1
输出:2
解释:
选择唯一的一列,两行都被覆盖了,因为整个矩阵都被覆盖了。
所以我们返回 2 。
算法1
(暴力枚举) $O(m*2^n)$
blablabla
时间复杂度
参考文献
C++ 代码
/*
遍历所有方案, 计算每种方案的最大覆盖行数,复杂度 2^n 。其中n为12
每次计算覆盖行数,
1. 先计算方案 select 合法,列数是否符合
2. 每个行判断是否完全覆盖,先用 line | select 求并集,再和方案做比较,看看是否相等。
比如有四列
分别用 0000~1111 表示方案选择,如果1的数量等于 numselect
*/
class Solution {
public:
int numofone(int i) {
int cnt = 0;
while(i) {
if (i & 1) cnt++;
i /= 2;
}
return cnt;
}
int maximumRows(vector<vector<int>>& matrix, int numSelect) {
int m = matrix.size();
int n = matrix[0].size();
vector<int> lines(m);
for (int i = 0; i < m ; i++) {
int v = 0;
for (auto item: matrix[i]) {
v = v * 2 + item;
}
lines[i] = v;
}
int ans = 0;
for (int i = 0 ; i < 1<<n; i++) {
if (numofone(i) == numSelect) {
int v = 0;
for (auto line: lines) {
if ( (line | i) == i) {
v++;
}
}
ans = max(ans, v);
}
}
return ans;
}
};