千问 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 ListInteger goodSubsetofBinaryMatrix(int[][] grid) {int m grid.length;int n grid[0].length;// 使用 HashMap 记录每种行状态压缩后的整数对应的行下标// 如果有多行状态相同只保留任意一个下标即可因为只需要返回一个解MapInteger, 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 为 0if (mask 0) {return Arrays.asList(i);}// 将当前行的状态存入 map如果状态已存在覆盖与否不影响最终寻找两行解的逻辑maskToIdx.put(mask, i);}// 情况2寻找两行它们的按位与结果为 0// 这意味着这两行在任何一列上都没有同时出现 1for (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)用于存储不同行状态的下标映射。