这道题的核心在于利用位运算和数学规律贪心来降低时间复杂度。 核心思路题目要求找到一个非空的行子集使得子集中每一列的元素和不超过子集大小的一半。直接暴力枚举所有子集2^m 种情况会超时但这道题有一个极其关键的数学性质如果存在一个大小 k ge 3 的好子集那么一定存在一个大小为 1 或 2 的好子集。因此我们只需要寻找以下两种情况即可1. 大小为 1 的好子集即矩阵中是否存在某一行它的所有元素都是 0。此时列和为 0满足 le lfloor 1/2 rfloor 0。2. 大小为 2 的好子集即是否存在两行它们在任意同一列上不同时为 1。如果两行在某列上同时为 1该列和为 2不满足 le lfloor 2/2 rfloor 1。这意味着两行的二进制表示下按位与的结果必须为 0。 Go 实现代码由于矩阵的列数 n 最多只有 5我们可以利用状态压缩将每一行压缩成一个整数用 5 位二进制即可表示。func goodSubsetofBinaryMatrix(grid [][]int) []int {m : len(grid)// 使用 map 记录每种行状态压缩后的整数对应的行下标// 如果有多行状态相同只保留任意一个下标即可因为只需要返回一个解maskToIdx : make(map[int]int)for i : 0; i m; i {mask : 0// 状态压缩将一行转换成一个整数for j : 0; j len(grid[i]); j {if grid[i][j] 1 {mask | (1 j)}}// 情况1找到了全为 0 的行mask 为 0if mask 0 {return []int{i}}// 将当前行的状态存入 mapmaskToIdx[mask] i}// 情况2寻找两行它们的按位与结果为 0// 这意味着这两行在任何一列上都没有同时出现 1for mask1, i : range maskToIdx {for mask2, j : range maskToIdx {if (mask1 mask2) 0 {// 题目要求返回升序的行下标if i j {return []int{i, j}}return []int{j, i}}}}// 如果找不到大小为 1 或 2 的好子集根据数学规律更大的子集也不存在return []int{}} 复杂度分析* 时间复杂度O(m cdot n U^2)。遍历矩阵进行状态压缩需要 O(m cdot n)。由于列数 n le 5不同的行状态最多只有 2^5 32 种即 U 32。双重循环遍历这些状态的时间是 O(32^2)这是一个极小的常数整体效率非常高。* 空间复杂度O(U)即 O(32)主要用于 maskToIdx 哈希表来存储不同行状态的下标映射。
