Hard

题目描述

给你一个下标从 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

解题思路

根据题目提示，如果存在好子集，那么一定存在长度为 1 或 2 的好子集。这大大简化了问题的复杂度。

分析过程：

  1. 长度为 1 的好子集：对于单行子集，每列的和最多为 floor(1/2) = 0，这意味着该行必须全为 0。

  2. 长度为 2 的好子集：对于两行子集，每列的和最多为 floor(2/2) = 1，这意味着两行在每一列上最多只能有一个 1。换句话说，两行的按位或结果中 1 的个数应该等于两行各自 1 的个数之和。

算法步骤：

  1. 首先检查是否存在全 0 行，如果存在则直接返回该行索引。

  2. 如果没有全 0 行，则尝试找到两行组成的好子集：

    • 将每行转换为位掩码（bitmask）
    • 使用哈希表存储每个位掩码对应的行索引
    • 遍历所有可能的位掩码对，检查它们是否能组成好子集
    • 两个位掩码 mask1 和 mask2 能组成好子集当且仅当 mask1 & mask2 == 0（即按位与为 0）

由于列数最多为 5，所以总共只有 2^5 = 32 种可能的位掩码，这使得算法非常高效。

代码实现

class Solution {
public:
    vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 检查是否有全0行
        for (int i = 0; i < m; i++) {
            bool allZero = true;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    allZero = false;
                    break;
                }
            }
            if (allZero) {
                return {i};
            }
        }
        
        // 将每行转换为位掩码并存储
        unordered_map<int, int> maskToRow;
        for (int i = 0; i < m; i++) {
            int mask = 0;
            for (int j = 0; j < n; j++) {
                mask |= (grid[i][j] << j);
            }
            maskToRow[mask] = i;
        }
        
        // 检查所有可能的位掩码对
        for (int mask1 = 0; mask1 < (1 << n); mask1++) {
            if (maskToRow.find(mask1) == maskToRow.end()) continue;
            for (int mask2 = mask1 + 1; mask2 < (1 << n); mask2++) {
                if (maskToRow.find(mask2) == maskToRow.end()) continue;
                if ((mask1 & mask2) == 0) {
                    int row1 = maskToRow[mask1];
                    int row2 = maskToRow[mask2];
                    if (row1 > row2) swap(row1, row2);
                    return {row1, row2};
                }
            }
        }
        
        return {};
    }
};

class Solution:
    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        
        # 检查是否有全0行
        for i in range(m):
            if all(grid[i][j] == 0 for j in range(n)):
                return [i]
        
        # 将每行转换为位掩码并存储
        mask_to_row = {}
        for i in range(m):
            mask = 0
            for j in range(n):
                mask |= (grid[i][j] << j)
            mask_to_row[mask] = i
        
        # 检查所有可能的位掩码对
        for mask1 in range(1 << n):
            if mask1 not in mask_to_row:
                continue
            for mask2 in range(mask1 + 1, 1 << n):
                if mask2 not in mask_to_row:
                    continue
                if mask1 & mask2 == 0:
                    row1, row2 = mask_to_row[mask1], mask_to_row[mask2]
                    return sorted([row1, row2])
        
        return []

public class Solution {
    public IList<int> GoodSubsetofBinaryMatrix(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        
        // 检查是否有全0行
        for (int i = 0; i < m; i++) {
            bool allZero = true;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    allZero = false;
                    break;
                }
            }
            if (allZero) {
                return new List<int> { i };
            }
        }
        
        // 将每行转换为位掩码并存储
        Dictionary<int, int> maskToRow = new Dictionary<int, int>();
        for (int i = 0; i < m; i++) {
            int mask = 0;
            for (int j = 0; j < n; j++) {
                mask |= (grid[i][j] << j);
            }
            maskToRow[mask] = i;
        }
        
        // 检查所有可能的位掩码对
        for (int mask1 = 0; mask1 < (1 << n); mask1++) {
            if (!maskToRow.ContainsKey(mask1)) continue;
            for (int mask2 = mask1 + 1; mask2 < (1 << n); mask2++) {
                if (!maskToRow.ContainsKey(mask2)) continue;
                if ((mask1 & mask2) == 0) {
                    int row1 = maskToRow[mask1];
                    int row2 = maskToRow[mask2];
                    if (row1 > row2) {
                        int temp = row1;
                        row1 = row2;
                        row2 = temp;
                    }
                    return new List<int> { row1, row2 };
                }
            }
        }
        
        return new List<int>();
    }
}

/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var goodSubsetofBinaryMatrix = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // Convert each row to a bitmask
    const masks = [];
    for (let i = 0; i < m; i++) {
        let mask = 0;
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                mask |= (1 << j);
            }
        }
        masks.push(mask);
    }
    
    // Check for single row solution (mask = 0)
    for (let i = 0; i < m; i++) {
        if (masks[i] === 0) {
            return [i];
        }
    }
    
    // Check for two row solution
    const seen = new Map();
    for (let i = 0; i < m; i++) {
        const mask = masks[i];
        
        // Check all possible submasks that when OR'd with current mask gives a valid result
        for (let submask = 0; submask < (1 << n); submask++) {
            if ((mask & submask) === 0) {
                if (seen.has(submask)) {
                    return [seen.get(submask), i];
                }
            }
        }
        seen.set(mask, i);
    }
    
    return [];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m × n + 2^(2n))
空间复杂度O(min(m, 2^n))

说明：

  • 时间复杂度：遍历矩阵需要 O(m × n)，构建哈希表需要 O(m × n)，检查所有位掩码对需要 O(2^(2n))。由于 n ≤ 5，所以 2^(2n) ≤ 1024，是常数级别的。
  • 空间复杂度：哈希表最多存储 min(m, 2^n) 个条目，因为不同的位掩码最多有 2^n 个。