本文涉及知识点
反证法 决策包容性 位运算、状态压缩、枚举子集汇总
LeetCode2732. 找到矩阵中的好子集
给你一个下标从 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.length
n == grid[i].length
1 <= m <= 104
1 <= n <= 5
grid[i][j] 要么是 0 ,要么是 1 。
决策包容性+反证法
假定某个合法解是选择k行。
性质一:k是奇数,且k >1,则一定存在k-1行的合法解。利用决策包容性来证明。则任意删除一行。 任意一列的和变小或不边。floor(k/2)和floor((k-1)/2)相等。
性质二:k是偶数,且k>2,一定存在k-2的合法解。利用反证法证明。从中任意选择k-2行,如果非法,则说某列,这k-2包括k/2个1。 → \rightarrow → 此列其它行全部为0 → \rightarrow → 除了选择这k-2行,选择其它k-2,此列都合法。
C k k − 2 = C k 2 = k × ( k − 2 ) / 2 C_{k}^{k-2}=C_{k}^2=k\times(k-2)/2 Ckk−2=Ck2=k×(k−2)/2 ,显然随着k递增而递增。k取最小值4,结果为6。即至少有6个不同列,和总共只有5列矛盾。
性质三:结合性质一性质二,如果k>=2,一定存在合法的2行解。
性质四:如果某行全为0,则可以只选择此行。
状态压缩
每行最多5列,值只能是0或1。可以用5位二进制的正数表示。
空间复杂度:O(2n)
如果不用子集状态压缩:
时间复杂度:O(2n2nm)
如果用子集状态压缩:
时间复杂度:O(3nm)
代码
核心代码
class Solution {
public:
vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
const int N = grid[0].size();
const int iMaskCount = 1 << N;
int i = -1;
vector<int> maskRow(iMaskCount,-1);
for (const auto& v : grid) {
i++;
int mask = 0;
for (const auto& n: v) {
mask = mask * 2 + n;
}
if (0 == mask) { return { i }; }
const int can = (~mask) & (iMaskCount - 1);
for (int sub = can; sub; sub = (sub - 1) & can) {
if (-1 != maskRow[sub]) {
return { maskRow[sub],i };
}
}
maskRow[mask] = i;
}
return {};
}
};
单元测试
template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
Assert::AreEqual(t1, t2);
}
template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
Assert::AreEqual(v1.size(), v2.size());
for (int i = 0; i < v1.size(); i++)
{
Assert::AreEqual(v1[i], v2[i]);
}
}
template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
sort(vv1.begin(), vv1.end());
sort(vv2.begin(), vv2.end());
Assert::AreEqual(vv1.size(), vv2.size());
for (int i = 0; i < vv1.size(); i++)
{
AssertEx(vv1[i], vv2[i]);
}
}
namespace UnitTest
{
vector<vector<int>> grid;
TEST_CLASS(UnitTest)
{
public:
TEST_METHOD(TestMethod0)
{
grid = { {0,1,1,0},{0,0,0,1},{1,1,1,1} };
auto res = Solution().goodSubsetofBinaryMatrix(grid);
AssertEx(vector<int>{0, 1}, res);
}
TEST_METHOD(TestMethod1)
{
grid = { {0} };
auto res = Solution().goodSubsetofBinaryMatrix(grid);
AssertEx(vector<int>{0}, res);
}
TEST_METHOD(TestMethod2)
{
grid = { {1,1,1},{1,1,1} };
auto res = Solution().goodSubsetofBinaryMatrix(grid);
AssertEx(vector<int>{}, res);
}
};
}
扩展阅读
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话 |
---|
《喜缺全书算法册》以原理、正确性证明、总结为主。 |
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。