2732、找到矩阵中的好子集

leetcode 数组数学哈希表矩阵位运算

Created At : 2024-06-27 16:23

Count:1k Views 👀 :

Comment:

题目
分析

TODO 需要复习

题目

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

分析

m 行 n 列。n 的范围是 $[0,5]$，需要详细分析。

题解来源：ßhttps://leetcode.cn/problems/find-a-good-subset-of-the-matrix/solutions/2305490/xiang-xi-fen-xi-wei-shi-yao-zhi-duo-kao-mbl6a/

元素哈希化，位运算

class Solution {
    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
        Map<Integer, Integer> maskToIdx = new HashMap<>();// 下标掩码
        // 计算 mask,将 1 转换成 
        for (int i = 0; i < grid.length; i++) {
            int mask = 0;
            for (int j = 0; j < grid[i].length; j++) {
                mask |= grid[i][j] << j;// 0保持不变，1 变成 2的j次方
            }
            if (mask == 0) {
                return List.of(i);
            }
            maskToIdx.put(mask, i);
        }

        for (Map.Entry<Integer, Integer> e1 : maskToIdx.entrySet()) { // 第一层遍历
            for (Map.Entry<Integer, Integer> e2 : maskToIdx.entrySet()) { // 第二层遍历
                if ((e1.getKey() & e2.getKey()) == 0) {
                    int i = e1.getValue();
                    int j = e2.getValue();
                    return i < j ? List.of(i, j) : List.of(j, i);
                }
            }
        }
        return List.of();
    }
}

使用数组哈希计算

空间换时间

class Solution {
    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
        int n = grid[0].length;
        int[] maskToIdx = new int[1 << n];
        Arrays.fill(maskToIdx, -1);
        int u = (1 << n) - 1;
        for (int i = 0; i < grid.length; i++) {
            int mask = 0;
            for (int j = 0; j < n; j++) {
                mask |= grid[i][j] << j;
            }
            if (mask == 0) {
                return List.of(i);
            }
            if (maskToIdx[mask] >= 0) {
                // 之前判断过，无需重复判断
                continue;
            }
            int c = u ^ mask; // mask 的补集
            for (int y = c; y > 0; y = (y - 1) & c) {
                int j = maskToIdx[y];
                if (j >= 0) {
                    return i < j ? List.of(i, j) : List.of(j, i);
                }
            }
            maskToIdx[mask] = i;
        }
        return List.of();
    }
}

状态压缩动态规划（SOSDP）

class Solution {
    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
        int n = grid[0].length;
        int[] f = new int[1 << n];
        Arrays.fill(f, -1);
        for (int i = 0; i < grid.length; i++) {
            int mask = 0;
            for (int j = 0; j < n; j++) {
                mask |= grid[i][j] << j;
            }
            if (mask == 0) {
                return List.of(i);
            }
            f[mask] = i;
        }

        int u = (1 << n) - 1;
        for (int s = 1; s < u; s++) {
            for (int b = 0; b < n; b++) {
                if ((s >> b & 1) == 0) {
                    continue;
                }
                f[s] = Math.max(f[s], f[s ^ (1 << b)]);
                int i = f[s];
                if (i < 0) {
                    continue;
                }
                int j = f[u ^ s];
                if (j >= 0) {
                    return i < j ? List.of(i, j) : List.of(j, i);
                }
            }
        }
        return List.of();
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com