2732. 找到矩阵中的好子集

发布于 2024-06-25  8 次阅读


给你一个下标从 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();
    }
}