千问 LeetCode 2732. 找到矩阵中的好子集 Go实现

这道题的核心在于利用位运算和数学规律（贪心）来降低时间复杂度。

💡 核心思路

题目要求找到一个非空的行子集，使得子集中每一列的元素和不超过子集大小的一半。直接暴力枚举所有子集（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 为 0）
if mask == 0 {
return []int{i}
}

// 将当前行的状态存入 map
maskToIdx[mask] = i
}

// 情况2：寻找两行，它们的按位与结果为 0
// 这意味着这两行在任何一列上都没有同时出现 1
for 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 哈希表来存储不同行状态的下标映射。