class Solution {
public:
vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
}
};
6463. 找到矩阵中的好子集
给你一个下标从 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 。原站题解
python3 解法, 执行用时: 132 ms, 内存消耗: 20.3 MB, 提交时间: 2024-06-25 09:22:34
class Solution:
def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
n = len(grid[0])
f = [-1] * (1 << n)
for i, row in enumerate(grid):
mask = 0
for j, x in enumerate(row):
mask |= x << j
if mask == 0:
return [i]
f[mask] = i
u = (1 << n) - 1
for s in range(1, u):
for b in range(n):
if (s >> b & 1) == 0:
continue
i = f[s] = max(f[s], f[s ^ (1 << b)])
if i < 0:
continue
j = f[u ^ s]
if j >= 0:
return sorted((i, j))
return []
java 解法, 执行用时: 2 ms, 内存消耗: 56.1 MB, 提交时间: 2024-06-25 09:22:09
class Solution {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
int n = grid[0].length;
int[] f = new int[1 << n];
Arrays.fill(f, -1);
for (int i = 0; i < grid.length; i++) {
int mask = 0;
for (int j = 0; j < n; j++) {
mask |= grid[i][j] << j;
}
if (mask == 0) {
return List.of(i);
}
f[mask] = i;
}
int u = (1 << n) - 1;
for (int s = 1; s < u; s++) {
for (int b = 0; b < n; b++) {
if ((s >> b & 1) == 0) {
continue;
}
f[s] = Math.max(f[s], f[s ^ (1 << b)]);
int i = f[s];
if (i < 0) {
continue;
}
int j = f[u ^ s];
if (j >= 0) {
return i < j ? List.of(i, j) : List.of(j, i);
}
}
}
return List.of();
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 56.1 MB, 提交时间: 2024-06-25 09:21:52
class Solution {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
int n = grid[0].length;
int[] maskToIdx = new int[1 << n];
Arrays.fill(maskToIdx, -1);
for (int i = 0; i < grid.length; i++) {
int mask = 0;
for (int j = 0; j < n; j++) {
mask |= grid[i][j] << j;
}
if (mask == 0) {
return List.of(i);
}
maskToIdx[mask] = i;
}
int u = (1 << n) - 1;
for (int x = 1; x < 1 << n; x++) {
int i = maskToIdx[x];
if (i < 0) {
continue;
}
int c = u ^ x;
for (int y = c; y > 0; y = (y - 1) & c) {
int j = maskToIdx[y];
if (j >= 0) {
return i < j ? List.of(i, j) : List.of(j, i);
}
}
}
return List.of();
}
}
python3 解法, 执行用时: 264 ms, 内存消耗: 19.6 MB, 提交时间: 2023-06-11 09:14:40
class Solution:
def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
n = len(grid[0])
table = {}
for r in range(len(grid)):
table[sum(grid[r][c]<<c for c in range(n))]=r
if 0 in table: return [table[0]] #这个特判还是得要，不然n=1就误判无解了
for x in range(1<<n):
for y in range(x+1,1<<n):
if x in table and y in table and x&y==0:
return [table[x],table[y]] if table[x]<table[y] else [table[y],table[x]]
return []
python3 解法, 执行用时: 172 ms, 内存消耗: 21 MB, 提交时间: 2023-06-11 09:14:04
class Solution:
def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
m,n = len(grid),len(grid[0])
states = defaultdict(list)
for i in range(m):
tmp = 0
for j in range(n):
tmp = tmp*2 + grid[i][j]
states[tmp].append(i)
# 贪心，开选
res = []
if states[0]:
return states[0]
tgt = 1 << n
ss = tgt - 1
# 枚举第一行
for lstate in range(tgt):
if not states[lstate]:
continue
# 补集
rstate = ss ^ lstate
s = rstate
# 获取补集的所有子集
while s:
if states[s]:
res = [states[lstate][0],states[s][0]]
res.sort()
return res
s = (s - 1) & rstate
return []
cpp 解法, 执行用时: 348 ms, 内存消耗: 132.7 MB, 提交时间: 2023-06-11 09:13:46
class Solution {
public:
vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
vector<int> a[1<<5];
vector<int> ans;
int m=grid.size();
int n=grid[0].size();
for(int i=0;i<m;i++){
int s=0;
for(auto c:grid[i])
s=(s<<1)+c;
if(s==0){
ans.push_back(i);
return ans;
}
a[s].push_back(i);
}
for(int i=0;i<(1<<n);i++){
if(a[i].size()==0)
continue;
for(int j=i+1;j<(1<<n);j++){
if(a[j].size()==0)
continue;
if((i&j)==0){
ans.push_back(a[i][0]);
ans.push_back(a[j][0]);
sort(ans.begin(),ans.end());
return ans;
}
}
}
return ans;
}
};
golang 解法, 执行用时: 328 ms, 内存消耗: 7.6 MB, 提交时间: 2023-06-11 09:13:12
func goodSubsetofBinaryMatrix(grid [][]int) []int {
nums := make([]int, 0)
n, m := len(grid), len(grid[0])
if n == 1 {
for i := 0; i < m; i ++ {
if grid[0][i] == 1 {
return []int{}
}
}
return []int{0}
}
for i := 0; i < n; i ++ {
var num int = 0
for j := 0; j < m; j ++ {
num = num * int(10) + int(grid[i][j])
}
nums = append(nums, num)
}
for i := 0; i < n; i ++ {
for j := i + 1; j < n; j ++ {
a1 := nums[i]
a2 := nums[j]
ok := true
for a1 > 0 || a2 > 0 {
if a1 % 10 == 1 && a2 % 10 == 1 {
ok = false
break
}
a1 /= 10
a2 /= 10
}
if ok {
return []int{i, j}
}
}
}
return []int{}
}