csdn推荐
题目
给你一个下标从 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]]
输出:[]
解释:没有办法得到一个好子集。
提示:
代码 完整代码
#include
#include
#include
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* goodSubsetofBinaryMatrix(int** grid, int gridSize, int* gridColSize, int* returnSize){
int m = gridSize;
int n = *gridColSize;
int* res = (int*)calloc(2, sizeof(int));
*returnSize = 0;
if(m == 1)
{
*returnSize = 1;
for (int i = 0; i < n; i++)
{
if(grid[0][i])
{
*returnSize = 0;
}
}
}
int *sum = (int*)calloc(m, sizeof(int));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
sum[i] += grid[i][j];
}
}
for (int i = 0; i < m; i++)
{
for (int j = i + 1; j < m; j++)
{
if(sum[i] + sum[j] <= n)
{
bool good = true;
for (int k = 0; k < n; k++)
{
if(grid[i][k] & grid[j][k])
{
good = false;
break;
}
}
if(good)
{
res[0] = i;
res[1] = j;
free(sum);
*returnSize = 2;
return res;
}
}
}
}
free(sum);
return res;
}
思路分析
这套代码用了枚举的方法。
整体思路是通过计算每一行的元素和,遍历所有可能的行对组合,检查是否满足好子集的条件。
每一列的限制:对于一个好子集,任何一列的和不能超过子集大小的一半。换句话说,对于任何一列,如果我们选择了一个 1,则我们必须选择足够的 0 来平衡,以确保该列的和不超过子集大小的一半。
总和限制:对于一个子集大小为 k,其所有列的和的总和不能超过 floor(k / 2) * n。这意味着每个选择的 1 都必须有相应的 0 来平衡,以确保满足好子集的条件。
好子集的存在性:为了证明在一个存在 n(n > 2)行好子集的集合中,一定至少存在两行可以构成好子集,我们可以通过反证法来证明这一点。
假设在一个存在 n 行(n > 2)好子集的集合中,没有任何两行可以构成好子集。
根据好子集的定义,对于一个包含 k 行的子集,任何一列的和至多为 floor(k / 2)。因此,如果选择的行数为 k,那么:
就此我们证明了在一个存在 n(n > 2)行好子集的集合中,一定至少存在两行可以构成好子集。
因此我们仅需寻找2行即可。
拆解分析 初始化和特殊情况处理
int* res = (int*)calloc(2, sizeof(int));
*returnSize = 0;
if(m == 1)
{
*returnSize = 1;
for (int i = 0; i < n; i++)
{
if(grid[0][i])
{
*returnSize = 0;
}
}
}
初始化结果数组 res 和返回大小 returnSize。处理特殊情况,当只有一行时,检查该行是否满足条件。
计算每一行的和
int *sum = (int*)calloc(m, sizeof(int));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
sum[i] += grid[i][j];
}
}
计算每一行的和并存储在数组 sum 中。
遍历所有行对组合,检查是否满足好子集条件
for (int i = 0; i < m; i++)
{
for (int j = i + 1; j < m; j++)
{
if(sum[i] + sum[j] <= n)
{
bool good = true;
for (int k = 0; k < n; k++)
{
if(grid[i][k] & grid[j][k])
{
good = false;
break;
}
}
if(good)
{
res[0] = i;
res[1] = j;
free(sum);
*returnSize = 2;
return res;
}
}
}
}
遍历所有行对组合,检查每一列是否满足条件。如果满足,则返回该行对组合。
复杂度分析 结果
文章来源:https://blog.csdn.net/qq_35085273/article/details/139961252
微信扫描下方的二维码阅读本文
暂无评论内容