1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# 2732. Find a Good Subset of the Matrix
"""
you are given a 0-indexed 'm n' binary matrix 'grid'. let us call a
non-empty subset of rows good if the sum of each column of the subset is at
most half of the length of the subset. more formally, if the length of the
chosen subset of rows is 'k', then the sum of each column should be at most
'floor(k / 2)'. return an integer array that contains row indices of a good
subset sorted in ascending order. if there are multiple answers, you can
return any of them. if there are no good subsets, return an empty array. a
subset of rows of the matrix 'grid' is any matrix that can be obtained by
deleting some (possibly none) rows from 'grid'
"""
class Solution(object):
def goodSubsetofBinaryMatrix(self, grid):
"""
:type grid: List[List[int]]
:rtype: List[int]
"""
if len(grid) == 1:
return [0] if all(num == 0 for num in grid[0]) else []
d = {}
for r, row in enumerate(grid):
num = sum(cell << c for c, cell in enumerate(row))
for i in range(32):
if (i & num) == 0 and i in d:
return [d[i], r]
d.setdefault(num, r)
return []
if __name__ == "__main__":
obj = Solution()
print(obj.goodSubsetofBinaryMatrix(grid=[[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 1, 1]]))
print(obj.goodSubsetofBinaryMatrix(grid=[[0]]))
print(obj.goodSubsetofBinaryMatrix(grid=[[1, 1, 1], [1, 1, 1]]))
|