找到矩阵中的好子集

标签: 贪心 位运算 数组 矩阵

难度: Hard

给你一个下标从 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 <= 104
  • 1 <= n <= 5
  • grid[i][j] 要么是 0 ，要么是 1 。

Submission

运行时间: 98 ms

内存: 20.0 MB

class Solution:
    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
        
        
        
        # my solution following public hint ... 98 ms ... 100 % ... 20.4 MB ... 14 %
        """
        如果存在好子集，其大小为k>=2，那么该好子集中必定存在【满足题意的、大小为2】的好子集的子集（反证法）
        """
        #  time: O(n)
        # space: O(n)
        
        n, m = len(grid), len(grid[0])
        seen = {}
        for i, arr in enumerate(grid):
            v = 0
            for d in arr:
                v = v * 2 + d
            if not v:
                return [i]
            seen[v] = i
        for a in range(2**m):
            if a not in seen:
                continue
            for b in range(2**m):
                if a != b and b in seen and not a & b:
                    return sorted([seen[a], seen[b]])
        return []

Explain

题解的核心思想是利用二进制表示每行的内容，并通过两两查找是否存在互不相交的行，即这两行在任何一列都没有同时出现1。首先，将每行的二进制数存入字典seen中，键是行的二进制数，值是行的索引。然后，对于字典中的每个键值对，检查是否存在两个不同的键（即两行），它们的二进制与操作结果为0，这代表这两行在任何一列都不会同时出现1。如果找到这样的两行，它们就构成一个好子集。如果所有行都被检查过后没有找到这样的两行，那么返回一个空数组。

时间复杂度: O(n*m + 4^m)

空间复杂度: O(2^m)

class Solution:
    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
        n, m = len(grid), len(grid[0])  # 获取行数和列数
        seen = {}  # 用于存储每行的二进制表示及其索引
        for i, arr in enumerate(grid):  # 遍历每一行
            v = 0  # 初始化二进制数
            for d in arr:  # 构造该行的二进制表示
                v = v * 2 + d
            if not v:  # 如果该行全为0，则直接返回这一行作为好子集
                return [i]
            seen[v] = i  # 存储行的二进制表示及索引
        for a in range(2**m):  # 遍历所有可能的二进制数作为行的二进制表示
            if a not in seen:  # 如果该二进制数不在seen中，则跳过
                continue
            for b in range(2**m):  # 再次遍历所有可能的二进制数
                if a != b and b in seen and not a & b:  # 如果找到两个互不相交的行
                    return sorted([seen[a], seen[b]])  # 返回它们的索引，按升序排序
        return []  # 如果没有找到任何好子集，则返回空数组

Explore

在算法中，通过遍历矩阵的每一行，然后使用一个循环将每行的元素（0或1）转换为一个二进制数，这个过程是精确的，可以保证每一行都被有效地转换成一个唯一的二进制数。这个二进制数是通过从左到右读取行中的元素并将其视为二进制位来构建的，其中`1`代表相应位置有元素，`0`代表没有。因此，通过这种方式可以确保每行数据的唯一性和正确的二进制表示。

在题解中，`seen`字典用来存储行的二进制表示及其索引。如果矩阵中有两行完全相同，则它们的二进制表示也会相同。在这种情况下，字典会覆盖之前存储的索引，因此只有最后一次出现的行索引会被保存。这确实可能导致某些好子集的遗漏，因为原始的多个好子集可能因为索引覆盖而无法完全识别出来。因此，为了更全面地维护所有行的信息，应该将`seen`字典中的值修改为索引列表而不是单个索引。

当前实现中，算法遍历了所有可能的二进制数（从0到2^m-1），其中m是矩阵的列数。对于每一个二进制数a，算法又遍历所有可能的二进制数b进行比较。这导致时间复杂度为O((2^m) * (2^m))，即O(4^m)，这在m较大时非常低效。存在更高效的方法，例如使用图论中的匹配算法来找出互不相交的行集合，或者利用动态规划和位运算结合的方法来优化查找过程。这些方法可以在保证找到解的同时显著减少计算量。