找到矩阵中的好子集

You are given a 0-indexed m x 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 good subsets, 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 or all) rows from grid.

 

Example 1:

Input: grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
Output: [0,1]
Explanation: We can choose the 0th and 1st rows to create a good subset of rows.
The length of the chosen subset is 2.
- The sum of the 0th column is 0 + 0 = 0, which is at most half of the length of the subset.
- The sum of the 1st column is 1 + 0 = 1, which is at most half of the length of the subset.
- The sum of the 2nd column is 1 + 0 = 1, which is at most half of the length of the subset.
- The sum of the 3rd column is 0 + 1 = 1, which is at most half of the length of the subset.

Example 2:

Input: grid = [[0]]
Output: [0]
Explanation: We can choose the 0th row to create a good subset of rows.
The length of the chosen subset is 1.
- The sum of the 0th column is 0, which is at most half of the length of the subset.

Example 3:

Input: grid = [[1,1,1],[1,1,1]]
Output: []
Explanation: It is impossible to choose any subset of rows to create a good subset.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m <= 104
• 1 <= n <= 5
• grid[i][j] is either 0 or 1.

// 思路：
// 1. 使用Java Stream来简化遍历和计算。
// 2. 通过Stream生成所有可能的行子集，并检查是否为好子集。
// 3. 返回满足条件的子集的行下标。

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public List<Integer> goodSubset(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        return IntStream.range(1, 1 << m)
                .mapToObj(i -> {
                    List<Integer> subset = new ArrayList<>();
                    int[] colSums = new int[n];
                    int k = 0;
                    for (int j = 0; j < m; j++) {
                        if ((i & (1 << j)) != 0) {
                            subset.add(j);
                            k++;
                            for (int l = 0; l < n; l++) {
                                colSums[l] += grid[j][l];
                            }
                        }
                    }
                    boolean isGoodSubset = IntStream.of(colSums).allMatch(sum -> sum <= k / 2);
                    return isGoodSubset ? subset : null;
                })
                .filter(subset -> subset != null)
                .findFirst()
                .orElse(new ArrayList<>());
    }
}

题解的核心思想是利用二进制表示每行的内容，并通过两两查找是否存在互不相交的行，即这两行在任何一列都没有同时出现1。首先，将每行的二进制数存入字典seen中，键是行的二进制数，值是行的索引。然后，对于字典中的每个键值对，检查是否存在两个不同的键（即两行），它们的二进制与操作结果为0，这代表这两行在任何一列都不会同时出现1。如果找到这样的两行，它们就构成一个好子集。如果所有行都被检查过后没有找到这样的两行，那么返回一个空数组。

O(n*m + 4^m)

O(2^m)