[每日一题] 2732.找到矩阵中的好子集

Richard

2024 年 06 月 25 日

87 次浏览

暂无评论

1891字数

LeetCode

> https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/description/?envType=daily-question&envId=2024-05-02

题目中 $n$ 的最大值为 5 ，且每个元素只可能是 0 或 1 ，因此可以分类讨论：

- 当好子集为一行时，所有列必须为 0 才可以满足条件；
- 当好子集为两行时，每列元素和不能超过 1 ，可以通过 and 运算判断；
- 当好子集为三行时，同样每列元素和不能超过 1 ，所以三行中任取两行也是好子集；
- 当好子集为四行时，这里也可以找到两行满足好子集。假设无法找到两行满足好子集，那么意味着任取两行都有一列相加为 2 。为了满足这个条件，至少需要 $C_4^2 = 6$ 列，而题目限制了列数最多为 5 ，因此必定有两行满足好子集。
- 当好子集为五行时，同理可以转化为两行。

这里算了一下暴力不会超时，所以直接写了个暴力法：

```c++
class Solution {
public:
    std::vector<int> goodSubsetofBinaryMatrix(std::vector<std::vector<int>>& grid) {
        const int n = grid.size(), m = grid[0].size();

for (int i = 0; i < n; i++) {
            bool isZero = true;
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    isZero = false;
                    break;
                }
            }

if (isZero)
                return {i};
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                bool exceed = false;
                for (int k = 0; k < m; k++) {
                    if (grid[i][k] & grid[j][k]) {
                        exceed = true;
                        break;
                    }
                }
                
                if (!exceed)
                    return {i, j};
            }
        }
        
        return {};
    }
};
```

- 时间复杂度：$O(m \times n^2)$ ，其中 $m, n$ 为数组 `grid` 的行列数。
- 空间复杂度：$O(1)$ 。

如果想要快一点可以遍历每一行，算出一个长为 $n$ 的二进制数，然后再进行位运算。由于 $m$ 最大为 $10^4$ 远大于 32 ，所以需要把二进制数去重，保存到一个哈希表中。

```c++
class Solution {
public:
    vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
        unordered_map<int, int> mask_to_idx;
        for (int i = 0; i < grid.size(); i++) {
            int mask = 0;
            for (int j = 0; j < grid[i].size(); j++) {
                mask |= grid[i][j] << j;
            }
            if (mask == 0) {
                return {i};
            }
            mask_to_idx[mask] = i;
        }

for (auto [x, i] : mask_to_idx) {
            for (auto [y, j] : mask_to_idx) {
                if ((x & y) == 0) {
                    return {min(i, j), max(i, j)};
                }
            }
        }
        return {};
    }
};
```

- 时间复杂度：$\mathcal{O}(mn+4^n)$ ，其中 $m$ 和 $n$ 分别为 $\textit{grid}$ 的行数和列数。
- 空间复杂度：$\mathcal{O}(2^n)$ 。至多有 $2^n$ 个不同的二进制数。

最后修改：2024 年 06 月 25 日