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

这是一道结合了位运算与数学规律（贪心）的巧妙题目。

💡 核心思路

题目要求找到一个非空的行子集，使得子集中每一列的元素和不超过子集大小的一半（即 le lfloor k/2 rfloor，其中 k 是选出的行数）。

直接暴力枚举所有子集（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。

🔍 为什么只需要考虑 1 行或 2 行？

* 1 行的情况：显然，只有全 0 的行才满足条件。
* 2 行的情况：只要两行在每一列上的和 le 1 即可。这意味着两行在二进制表示下，按位与（&）的结果必须为 0。
* 3 行及以上的情况：题目中矩阵的列数 n 最多只有 5。根据抽屉原理和反证法可以证明，如果存在一个更大的好子集，我们总能从中抽离出满足条件的 1 行或 2 行。因此，只要找不到 1 行或 2 行的解，更大的解也一定不存在。

💻 Java 实现代码

我们可以利用状态压缩，将每一行压缩成一个整数（因为最多只有 5 列，用 5 位二进制即可表示）。

import java.util.*;

class Solution {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;

// 使用 HashMap 记录每种行状态（压缩后的整数）对应的行下标
// 如果有多行状态相同，只保留任意一个下标即可（因为只需要返回一个解）
Map<Integer, Integer> maskToIdx = new HashMap<>();

for (int i = 0; i < m; i++) {
int mask = 0;
// 状态压缩：将一行转换成一个整数
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
mask |= (1 << j);
}
}

// 情况1：找到了全为 0 的行（mask 为 0）
if (mask == 0) {
return Arrays.asList(i);
}

// 将当前行的状态存入 map（如果状态已存在，覆盖与否不影响最终寻找两行解的逻辑）
maskToIdx.put(mask, i);
}

// 情况2：寻找两行，它们的按位与结果为 0
// 这意味着这两行在任何一列上都没有同时出现 1
for (int mask1 : maskToIdx.keySet()) {
for (int mask2 : maskToIdx.keySet()) {
if ((mask1 & mask2) == 0) {
int i = maskToIdx.get(mask1);
int j = maskToIdx.get(mask2);
// 题目要求返回升序的行下标
if (i == j) continue; // 防止取到同一行（虽然全0行在上面已经返回了，这里防御一下）
return i < j ? Arrays.asList(i, j) : Arrays.asList(j, i);
}
}
}

// 如果找不到大小为 1 或 2 的好子集，根据数学规律，更大的子集也不存在
return new ArrayList<>();
}
}

📊 复杂度分析

* 时间复杂度：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)，用于存储不同行状态的下标映射。