2732. 找到矩阵中的好子集

Powered by:NEFU AB-IN

Link

2732. 找到矩阵中的好子集

• 题意

给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。

从原矩阵中选出若干行构成一个行的 非空 子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 好子集。

更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。

请你返回一个整数数组，它包含好子集的行下标，请你将其 升序 返回。

如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。

一个矩阵 grid 的行 子集 ，是删除 grid 中某些（也可能不删除）行后，剩余行构成的元素集合。

• 思路

由于数组中的元素类型只有0和1，列最多五行，那么可以举行的个数的例子
比如如果一行全是0，是可行的；比如 01010 与 10101这种互补的形式，或者01010和 00001这种，也是成立
如果答案是三行，那么肯定包括一行和两行的情况，所以只需要考虑1,2行，2行的时候考虑二进制逐位与运算

• 代码

# import
from functools import cache
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
from types import GeneratorType
from typing import TypeVar, List, Dict, Any, Callable# Data structure
class SA:def __init__(self, x, y):self.x = xself.y = ydef __lt__(self, other):return self.x < other.x# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
E = int(100)# Set recursion limit
setrecursionlimit(INF)# Read
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
read_list = lambda: list(map(int, input().split()))# Func
class std:# Recursion@staticmethoddef bootstrap(f, stack=None):if stack is None:stack = []def wrappedfunc(*args, **kwargs):if stack:return f(*args, **kwargs)else:to = f(*args, **kwargs)while True:if isinstance(to, GeneratorType):stack.append(to)to = next(to)else:stack.pop()if not stack:breakto = stack[-1].send(to)return toreturn wrappedfuncletter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> Aarray = staticmethod(lambda x=0, size=N: [x] * size)array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])max = staticmethod(lambda a, b: a if a > b else b)min = staticmethod(lambda a, b: a if a < b else b)filter = staticmethod(lambda func, iterable: list(filter(func, iterable)))# —————————————————————Division line ——————————————————————class Solution:def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:# 挑一行n, m = len(grid), len(grid[0])for i in range(n):row = grid[i]if sum(row) == 0:return [i]# 挑两行binary_map = {}for i in range(n):row_binary = int("".join(map(str, grid[i])), 2)for existing_row_binary, index in binary_map.items():if row_binary & existing_row_binary == 0:  # 逐位与运算return sorted([index, i])binary_map[row_binary] = ireturn []