| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2239 |
第 106 场双周赛 Q4 |
|
给你一个下标从 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.lengthn == grid[i].length1 <= m <= 1041 <= n <= 5grid[i][j]要么是0，要么是1。
我们可以从小到大考虑答案选择的行数
- 如果
$k = 1$ ，每一列的和最大为$0$ ，那么必须满足有一行的所有元素都是$0$ ，否则无法满足条件。 - 如果
$k = 2$ ，每一列的和最大为$1$ ，那么必须存在有两行，且这两行的元素按位与之后的结果是$0$ ，否则无法满足条件。 - 如果
$k = 3$ ，每一列的和最大也是$1$ 。如果$k = 2$ 不满足条件，那么$k = 3$ 也一定不满足条件，所以我们不需要考虑所有$k \gt 2$ 且$k$ 为奇数的情况。 - 如果
$k = 4$ ，每一列的和最大为$2$ ，此时一定是$k = 2$ 不满足条件，也就是说，任意选取两行，都存在至少一个列的和为$2$ 。我们在$4$ 行中任意选取$2$ 行，一共有$C_4^2 = 6$ 种选法，那么存在至少$6$ 个$2$ 的列。由于列数$n \le 5$ ，所以一定存在至少一列的和大于$2$ ，所以$k = 4$ 也不满足条件。 - 对于
$k \gt 4$ 且$k$ 为偶数的情况，我们可以得出同样的结论，即$k$ 一定不满足条件。
综上所述，我们只需要考虑
时间复杂度
class Solution:
def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
g = {}
for i, row in enumerate(grid):
mask = 0
for j, x in enumerate(row):
mask |= x << j
if mask == 0:
return [i]
g[mask] = i
for a, i in g.items():
for b, j in g.items():
if (a & b) == 0:
return sorted([i, j])
return []class Solution {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
Map<Integer, Integer> g = new HashMap<>();
for (int i = 0; i < grid.length; ++i) {
int mask = 0;
for (int j = 0; j < grid[0].length; ++j) {
mask |= grid[i][j] << j;
}
if (mask == 0) {
return List.of(i);
}
g.put(mask, i);
}
for (var e1 : g.entrySet()) {
for (var e2 : g.entrySet()) {
if ((e1.getKey() & e2.getKey()) == 0) {
int i = e1.getValue(), j = e2.getValue();
return List.of(Math.min(i, j), Math.max(i, j));
}
}
}
return List.of();
}
}class Solution {
public:
vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
unordered_map<int, int> g;
for (int i = 0; i < grid.size(); ++i) {
int mask = 0;
for (int j = 0; j < grid[0].size(); ++j) {
mask |= grid[i][j] << j;
}
if (mask == 0) {
return {i};
}
g[mask] = i;
}
for (auto& [a, i] : g) {
for (auto& [b, j] : g) {
if ((a & b) == 0) {
return {min(i, j), max(i, j)};
}
}
}
return {};
}
};func goodSubsetofBinaryMatrix(grid [][]int) []int {
g := map[int]int{}
for i, row := range grid {
mask := 0
for j, x := range row {
mask |= x << j
}
if mask == 0 {
return []int{i}
}
g[mask] = i
}
for a, i := range g {
for b, j := range g {
if a&b == 0 {
return []int{min(i, j), max(i, j)}
}
}
}
return []int{}
}function goodSubsetofBinaryMatrix(grid: number[][]): number[] {
const g: Map<number, number> = new Map();
const m = grid.length;
const n = grid[0].length;
for (let i = 0; i < m; ++i) {
let mask = 0;
for (let j = 0; j < n; ++j) {
mask |= grid[i][j] << j;
}
if (!mask) {
return [i];
}
g.set(mask, i);
}
for (const [a, i] of g.entries()) {
for (const [b, j] of g.entries()) {
if ((a & b) === 0) {
return [Math.min(i, j), Math.max(i, j)];
}
}
}
return [];
}use std::collections::HashMap;
impl Solution {
pub fn good_subsetof_binary_matrix(grid: Vec<Vec<i32>>) -> Vec<i32> {
let mut g: HashMap<i32, i32> = HashMap::new();
for (i, row) in grid.iter().enumerate() {
let mut mask = 0;
for (j, &x) in row.iter().enumerate() {
mask |= x << j;
}
if mask == 0 {
return vec![i as i32];
}
g.insert(mask, i as i32);
}
for (&a, &i) in g.iter() {
for (&b, &j) in g.iter() {
if (a & b) == 0 {
return vec![i.min(j), i.max(j)];
}
}
}
vec![]
}
}