给你一个下标从 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]]
输出:[]
解释:没有办法得到一个好子集。
思路:
由于矩阵元素值只有 0 和 1,对于矩阵的每一行,把这一行看成一个二进制数。
- 如果答案只有 1 行,根据题目要求,每一列的和至多为 ⌊1/2⌋=0\,也就是这一行必须全为 0。
- 如果答案有 2 行,每一列的和至多为 ⌊2/2⌋=1,所以同一列至多有一个 111,不能有两个 1。从二进制角度来理解,就是这两行对应二进制数的 AND 等于 0。
- 如果答案有 3 行,每一列的和至多为 ⌊3/2⌋=1,这和 2 行的情况是一样的。如果可以选 3 行,那么必然也可以选 2 行,所以无需考虑答案有 3 行的情况。
- 如果答案超过 4 行,下面细说。
以下讨论的前提是,不存在小于 4 行的答案。
设答案有kk 行(k≥4)。
性质一:每一列的和至多为 k/2。
性质二:任意 2 行的 AND 均不为 0(否则答案可以是 2 行)。
性质三:根据性质一,总的 1 的个数至多为 kn/2,所以每一行的 1 的个数的平均值是 n/2。由于最小值不超过平均值,所以 1 的个数最少的那一行,至多有 n/2 个 1。
分类讨论:
- 如果 n≤3,那么 1 的个数最少的那一行只有一个 1。不妨假设 1 在第一列,根据性质二,其余每一行的第一列都必须是 1,与性质一矛盾。
- 否则,由于 n≤5,那么 1 的个数最少的那一行有两个 1。不妨假设这两个 1 在第一列和第二列,根据性质二,其余每一行的第一列或第二列必须有 1,那么前两列总共至少有 k+1 个 1,但是性质一告诉我们前两列至多有 k/2⋅2=k 个 1,矛盾。
所以如果不存在小于 4 行的答案,那么也不会存在 ≥4 行的答案。
综上所述,在 n≤5 的数据范围下,只需考虑答案为 1 行或者 2 行的情况(3 行的情况转换成 2 行),如果不存在 1 行和 2 行的答案,则无解。
class Solution {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
Map<Integer,Integer> mask = new HashMap<>();
for(int i = 0;i < grid.length;i++){
int m = 0;
for(int j = 0;j < grid[0].length;j++){
m |= grid[i][j] << j;
}
if(m == 0){
return List.of(i);
}
mask.put(m,i);
}
for(Map.Entry<Integer,Integer> e1 : mask.entrySet()){
for(Map.Entry<Integer,Integer> e2 : mask.entrySet()){
if((e1.getKey() & e2.getKey()) == 0){
int i = e1.getValue();
int j = e2.getValue();
return i < j ? List.of(i,j) : List.of(j,i);
}
}
}
return List.of();
}
}
Comments NOTHING