题干描述：
给你一个下标从 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 X n’的二进制矩阵‘grid’。我们需要找到矩阵中的若干行组成的一个非空子集，如果子集中任何一列的和至多为自己大小的一半，那么我们称这个子集是“好子集”。要求返回这个子集的行下标，按照升序排列。如果有多个子集，返回任意一个；如果没有好子集，则返回一个空数组。
题目理解：
对以上题目简单理解后我们就知道，我们需要找到一个二进制矩阵的若干行构成的一个非空子集，使得子集中任何一列的和至多为子集大小的一半。具体来说就是如果子集的大小是‘k’，则每列的和不能超过‘floor（k/2）’。
解题思路：
为了找到符合条件的自己，我们可以采用如下思路：
1.转化每行表示
我们将每一行的二进制形式转化为一个整数。举个例子就是，如果一行是【0,1,0】，那么我们可以将其表示为2（即010的十进制形式）。上面这种转换的好处是可以利用按位运算来简化检查行与行之间是否有着重叠的‘1’。
// 定义哈希表项结构
typedef struct {
int key; // 用于存储行转换后的整数表示
int val; // 用于存储原始行的索引
UT_hash_handle hh; // 用于uthash库的哈希句柄
} HashItem;
// 将每一行转化为一个整数，并存储在哈希表中
void convertAndStoreRows(int** grid, int gridSize, int* gridColSize, HashItem** mp) {
int m = gridSize;
int n = gridColSize[0];
for (int j = 0; j < m; j++) {
int st = 0;
for (int i = 0; i < n; i++) {
st |= (grid[j][i] << i); // 将第i列的值左移i位，然后按位或运算
}
hashAddItem(mp, st, j); // 将行的整数表示及索引添加到哈希表中
}
}
2.存储行的整数表示和索引
使用一个哈希表用于存储每一航班的整数表示及其在原矩阵中的索引以便于快速查找和进行比较。
3.检查行子集
首先，检查是否存在全为0的行，若存在这样的行，它本身就是一个满足条件的好子集，因为它不会影响任何列的和。然后检查两行的组合，看看是否存在两行的按位于结果为0，若存在，则这两行的每列和都满足条件。（这里我们简单解释一下为什么当按位与结果为0时，每列和都满足条件，这是因为当两行按位与结果为0时则意味着这两行在任何一列上都没有同时为1的情况。换句话说就是，这两行在同一列上不会同时有两个1，因此它们在同一列上的和最多为1。由于我们只需要自己大小为2的情况，因此每列的和至多为1）
// 检查是否有两行按位与运算结果为0
int* findGoodSubset(HashItem* mp, int* returnSize) {
int* ans = NULL;
HashItem *pEntry1, *pEntry2, *tmp;
// 如果有一行全为0，直接返回该行
if (hashFindItem(&mp, 0)) {
ans = (int*)malloc(sizeof(int));
ans[0] = hashGetItem(&mp, 0, 0); // 获取该行的索引
*returnSize = 1;
return ans;
}
// 检查两行组合是否满足条件
HASH_ITER(hh, mp, pEntry1, tmp) {
int x = pEntry1->key, i = pEntry1->val;
HASH_ITER(hh, mp, pEntry2, tmp) {
int y = pEntry2->key, j = pEntry2->val;
if (i != j && !(x & y)) { // 如果按位与结果为0，且不是同一行
ans = (int*)malloc(sizeof(int) * 2);
ans[0] = fmin(i, j); // 返回索引较小的行
ans[1] = fmax(i, j); // 返回索引较大的行
*returnSize = 2;
return ans;
}
}
}
// 如果没有找到符合条件的行子集，返回空数组
*returnSize = 0;
return ans;
}
4.返回结果
如果找到满足条件的自己，返回它们的行下标；若没有找到满足条件的子集，返回一个空数组。
完整的代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include "uthash.h" // 确保uthash.h文件与此源文件在同一目录下
// 定义哈希表项结构
typedef struct {
int key; // 用于存储行转换后的整数表示
int val; // 用于存储原始行的索引
UT_hash_handle hh; // 用于uthash库的哈希句柄
} HashItem;
// 查找哈希表中的项
HashItem* hashFindItem(HashItem** obj, int key) {
HashItem* pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry); // 根据key查找项
return pEntry;
}
// 添加项到哈希表
bool hashAddItem(HashItem** obj, int key, int val) {
if (hashFindItem(obj, key)) {
return false; // 如果项已经存在，则返回false
}
HashItem* pEntry = (HashItem*)malloc(sizeof(HashItem));
pEntry->key = key;
pEntry->val = val;
HASH_ADD_INT(*obj, key, pEntry); // 将项添加到哈希表
return true;
}
// 设置哈希表中的项
bool hashSetItem(HashItem** obj, int key, int val) {
HashItem* pEntry = hashFindItem(obj, key);
if (!pEntry) {
hashAddItem(obj, key, val); // 如果项不存在，则添加新项
}
else {
pEntry->val = val; // 如果项存在，则更新项的值
}
return true;
}
// 获取哈希表中的项
int hashGetItem(HashItem** obj, int key, int defaultVal) {
HashItem* pEntry = hashFindItem(obj, key);
if (!pEntry) {
return defaultVal; // 如果项不存在，则返回默认值
}
return pEntry->val;
}
// 释放哈希表内存
void hashFree(HashItem** obj) {
HashItem* curr, * tmp;
HASH_ITER(hh, *obj, curr, tmp) { // 迭代哈希表中的所有项
HASH_DEL(*obj, curr);
free(curr); // 释放每项的内存
}
}
// 主函数，找到符合条件的行子集
int* goodSubsetofBinaryMatrix(int** grid, int gridSize, int* gridColSize, int* returnSize) {
int* ans = NULL;
HashItem* mp = NULL; // 哈希表，用于存储每行的整数表示及其索引
int m = gridSize;
int n = gridColSize[0];
// 将每一行转化为一个整数，并存储在哈希表中
for (int j = 0; j < m; j++) {
int st = 0;
for (int i = 0; i < n; i++) {
st |= (grid[j][i] << i); // 将第i列的值左移i位，然后按位或运算
}
hashAddItem(&mp, st, j); // 将行的整数表示及索引添加到哈希表中
}
// 如果有一行全为0，直接返回该行
if (hashFindItem(&mp, 0)) {
ans = (int*)malloc(sizeof(int));
ans[0] = hashGetItem(&mp, 0, 0); // 获取该行的索引
*returnSize = 1;
hashFree(&mp); // 释放哈希表内存
return ans;
}
// 检查是否有两行按位与运算结果为0
HashItem* pEntry1, * pEntry2, * tmp;
HASH_ITER(hh, mp, pEntry1, tmp) {
int x = pEntry1->key, i = pEntry1->val;
HASH_ITER(hh, mp, pEntry2, tmp) {
int y = pEntry2->key, j = pEntry2->val;
if (i != j && !(x & y)) { // 如果按位与结果为0，且不是同一行，表示两行没有公共1的列
ans = (int*)malloc(sizeof(int) * 2);
ans[0] = fmin(i, j); // 返回索引较小的行
ans[1] = fmax(i, j); // 返回索引较大的行
*returnSize = 2;
hashFree(&mp); // 释放哈希表内存
return ans;
}
}
}
// 如果没有找到符合条件的行子集，返回空数组
*returnSize = 0;
hashFree(&mp); // 释放哈希表内存
return ans;
}
// 测试函数
int main() {
int gridSize = 3;
int gridColSize[3] = { 3, 3, 3 };
int gridData[3][3] = {
{0, 1, 0},
{1, 0, 0},
{1, 1, 1}
};
int* grid[3];
for (int i = 0; i < 3; i++) {
grid[i] = gridData[i];
}
int returnSize;
int* result = goodSubsetofBinaryMatrix(grid, gridSize, gridColSize, &returnSize);
printf("Result size: %d\n", returnSize);
if (returnSize > 0) {
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
}
else {
printf("No valid subset found.\n");
}
if (result != NULL) {
free(result);
}
return 0;
}
