目标
给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。
从原矩阵中选出若干行构成一个行的 非空 子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 好子集。
更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。
请你返回一个整数数组，它包含好子集的行下标，请你将子集中的元素 升序 返回。
如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。
一个矩阵 grid 的行 子集 ，是删除 grid 中某些（也可能不删除）行后，剩余行构成的元素集合。
示例 1：
输入：grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
输出：[0,1]
解释：我们可以选择第 0 和第 1 行构成一个好子集。
选出来的子集大小为 2 。
- 第 0 列的和为 0 + 0 = 0 ，小于等于子集大小的一半。
- 第 1 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 2 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 3 列的和为 0 + 1 = 1 ，小于等于子集大小的一半。示例 2：
输入：grid = [[0]]
输出：[0]
解释：我们可以选择第 0 行构成一个好子集。
选出来的子集大小为 1 。
- 第 0 列的和为 0 ，小于等于子集大小的一半。示例 3：
输入：grid = [[1,1,1],[1,1,1]]
输出：[]
解释：没有办法得到一个好子集。说明：
- m == grid.length
- n == grid[i].length
- 1 <= m <= 10^4
- 1 <= n <= 5
grid[i][j]要么是 0 ，要么是 1 。
思路
有一个 m*n 的 二进制矩阵，任选k行，如果每一列的和不大于 k/2，则称为矩阵的好子集，返回任意一个好子集行标的集合。
在写这篇题解的时候才注意到是二进制矩阵，即元素值不是0就是1。这道题是根据提示写的，如果存在好子集则一定存在k为1或2的好子集，然后就根据好子集的要求循环判断。
当k为1时，好子集元素值全为0.当k为2时，任选两行遍历列判断是否有和大于1。
// todo 看一下题解
代码
/**
* @date 2024-06-25 0:28
*/
public class GoodSubsetofBinaryMatrix2732 {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
List<Integer> list = new ArrayList<>();
Queue<Integer> queue = new ArrayDeque<>();
here:
for (int i = 0; i < m; i++) {
queue.offer(i);
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
continue here;
}
}
list.add(i);
}
if (list.size() > 0) {
return list;
}
while (!queue.isEmpty()) {
int i = queue.poll();
here:
for (int j = i + 1; j < m; j++) {
for (int k = 0; k < n; k++) {
if (grid[i][k] + grid[j][k] > 1){
continue here;
}
}
list.add(i);
list.add(j);
return list;
}
}
return list;
}
}
性能
