LeetCode 1252：从矩阵模拟到公式推导，奇数值单元格计数优化

LeetCode 1252Cells with Odd Values in a Matrix中文题名叫奇数值单元格的数目。这题在题库里不算难但它很有意思——第一次我老老实实建了个二维矩阵模拟提交成绩平平改成“行、列操作拆分统计”之后直接拿到了耗时 100、内存 98 的结果。这篇题解把从暴力模拟到数学公式的完整思考链路重新走一遍适合刚刷矩阵类题目的新人也适合已经会做、但想搞明白“为什么能这么快”的老手。1. 先别急着开矩阵这题真正的考点是“拆开计数”1.1 暴力模拟不是不行只是思路会糊住你先看题目本身。给你一个 m x n 的矩阵初始全是 0再给一个数组indices其中每个元素是[ri, ci]表示一次操作里要把所有满足i ri的行整行加 1同时也把所有满足j ci的列整列加 1。所有操作做完以后统计整个矩阵里有多少个格子数值是奇数。注意这里的关键点indices里每一项是“行和列同时加 1”不是二选一。我第一次读题时还恍惚了一下后来反复确认才明白。很多人拿到题的第一反应是建一个vectorvectorint matrix(m, vectorint(n, 0))然后遍历indices遇到一行就把这一行每个元素 遇到一列就把这一列每个元素 最后再双层循环数奇数。这种写法没有任何技术含量不过因为题目给出的 m、n 最大只有 50indices长度最大也只有 100所以暴力照样能过LeetCode 上大量提交就是这么过的。但暴力的问题在于它把一个原本可以“算”的题变成了“模拟”的题。矩阵里的每个格子都可能被修改多次而最后一次遍历统计时还要重新扫一遍二维数组。这里的时间复杂度是O(L*(mn) mn)其中 L 是indices的长度。虽然题目限制下完全可行但它不是最优解。更关键的是如果你习惯了这种上来就开矩阵的做法以后遇到 n、m 上到 1e5 的同类题就直接无从下手了。方案时间空间提交表现二维矩阵模拟O(L*(mn) mn)O(mn)能过但时间和内存都在 60% 左右行列数组统计 遍历矩阵判断O(L m n mn)O(mn)内存好时间中上行列数组统计 公式直接计算O(L m n)O(mn)时间 100内存 98从表格能直观看到差别不在常数项而在有没有跳出“矩阵必须真实存在”的惯性。1.2 关键观察每个操作可以拆成“行 1”和“列 1”我们要优化就要抓住问题的本质。一次[ri, ci]操作做的事情等价于两件独立的事第ri行被操作了一次第ci列被操作了一次。行和列是两个独立维度它们对格子的影响是叠加的。于是可以开两个一维数组rowCount[m]记录每一行总共被操作了多少次colCount[n]记录每一列总共被操作了多少次遍历一遍indices把rowCount[ri]、colCount[ci]这就是 O(L)。之后格子(i, j)的最终值是什么就是rowCount[i] colCount[j]。为什么因为每个格子只受两种外力影响所在行的增长、所在列的增长。一个格子既不会因为其他行的操作而变也不会因为其他列的操作而变。这是矩阵行列操作的“独立性”。想明白这一点就不再需要真的去维护一个二维矩阵了。2. 用一张表验证“单元格值 行次数 列次数”2.1 手推一遍官方示例搞清楚操作顺序问题官方给的第一个示例是m 2, n 3, indices [[0,1],[1,1]]预期输出 6。我建议你拿笔手动推一遍很多细节会暴露出来。我按“先执行行操作、再执行列操作”的顺序来模拟步骤操作内容矩阵状态初始无[[0,0,0],[0,0,0]]操作1 行部分第 0 行全部 1[[1,1,1],[0,0,0]]操作1 列部分第 1 列全部 1[[1,2,1],[0,1,0]]操作2 行部分第 1 行全部 1[[1,2,1],[1,2,1]]操作2 列部分第 1 列全部 1[[1,3,1],[1,3,1]]最终矩阵里 6 个格子全是奇数所以答案是 6。这里有个问题值得讨论操作的“先后顺序”会不会影响最终结果比如先做列部分再做行部分结果会不一样吗我试了一下结果完全一样。原因在于一个操作中的行影响集和列影响集交集恰好只有一个格子(ri, ci)这个格子无论先被行加还是先被列加净效果都是加 2而其他格子要么只被行加到要么只被列加到。加法是可交换的所以顺序无关紧要。这一点在做题时可以放心但最好自己推一遍不要等到面试现场才去怀疑。再看用行列数组怎么得到 6rowCount [1, 1]两行各被操作 1 次colCount [0, 2, 0]第 1 列被操作了 2 次第一次和第二次操作都包含列 1然后逐个格子套rowCount[i] colCount[j](0,0)101奇数(0,1)123奇数(0,2)101奇数(1,0)101奇数(1,1)123奇数(1,2)101奇数和模拟结果完全一致。所以“单元格值 该行累计操作次数 该列累计操作次数”这个核心公式是可靠的。只要它成立后续所有数学化简都有了地基。2.2 奇偶性跳板行、列次数必须“一奇一偶”我们已经知道格子值 行次数 列次数。现在问题变成怎么快速判断rowCount[i] colCount[j]是不是奇数这里只需要一个初中数学结论奇偶性相加只有“奇偶”或者“偶奇”才是奇数两个奇数相加是偶数两个偶数相加也是偶数。换句话说一个格子最终是奇数当且仅当它所在的行被操作了奇数次且所在的列被操作了偶数次或者反过来行是偶数次、列是奇数次。行和列必须“一奇一偶”没有第三种情况。这个观察直接把问题从“每个格子都算一遍”变成“统计两类行、两类列的数量”。我们把“被操作了奇数次的行的数量”记为oddRows把“被操作了奇数次的列的数量”记为oddCols。那么剩下的m - oddRows行就是偶次数行n - oddCols列就是偶次数列。接下来要做的就是把oddRows、oddCols和一个二维矩阵里的格子数量建立关系。这里不再需要枚举具体是哪些行、哪些列只需要数量因为题目只要求数奇数格子不要求输出坐标。3. 从行数、列数直接推出答案的那个公式3.1 推导一按两类格子分别计数上一节已经定了基调奇数值格子只可能出现在两类位置。第一类是“奇数行 偶数列”的格子里第二类是“偶数行 奇数列”的格子里。两类互不重叠所以总数等于两类之和。先看第一类。奇数行的数量是oddRows偶数列的数量是n - oddCols。任意选一个奇数行、任意选一个偶数列就能确定一个格子所以这类格子有oddRows * (n - oddCols)再看第二类。偶数行的数量是m - oddRows奇数列的数量是oddCols所以这类格子有(m - oddRows) * oddCols总数就是ans oddRows * (n - oddCols) (m - oddRows) * oddCols这个式子先不要急着展开因为展开后的形式更容易算不展开也能直接代入。拿刚才的官方示例验证m2, n3, oddRows2, oddCols0代入ans 2 * (3 - 0) (2 - 2) * 0 6一次通过。再看官方另一个示例m 2, n 2, indices [[1,1],[0,0]]。推一下行、列操作次数第 1 行出现 1 次第 0 行出现 1 次所以rowCount [1, 1]oddRows 2第 1 列出现 1 次第 0 列出现 1 次所以colCount [1, 1]oddCols 2代入公式ans 2 * (2 - 2) (2 - 2) * 2 0两个示例都验证通过。这至少说明公式方向是对的不会出现“样例都过不了”的尴尬。3.2 推导二全集加减交叉项防止背公式翻车公式oddRows * (n - oddCols) (m - oddRows) * oddCols是从分类视角推的。还有一种更不容易漏项的推导方式我更喜欢讲给读者听。想象一下如果把所有奇数行全部先算进来不管列是什么有多少个格子答案是oddRows * n也就是“奇数行覆盖的格子总数”。这些格子里有些其实不是答案因为如果列也是奇数次那么“奇奇偶”格子就得淘汰。类似地把所有奇数列全部先算进来有oddCols * m个格子。这里面也混着“行也是奇数次”的格子同样要淘汰。关键来了那些“行、列都是奇数”的交叉格子在前一次计数里被算了一次在后一次计数里又被算了一次总共被加了两次。但最终答案不需要它们所以要把它们减掉两次。交叉格子的数量是多少就是oddRows * oddCols因为每一对“奇数行 × 奇数列”都唯一对应一个交叉格子。于是得到ans oddRows * n oddCols * m - 2 * oddRows * oddCols把这两个式子对比一下oddRows * (n - oddCols) (m - oddRows) * oddCols oddRows*n - oddRows*oddCols m*oddCols - oddRows*oddCols oddRows*n oddCols*m - 2*oddRows*oddCols完全等价。我实际做题时更喜欢用展开后的形式因为可以省掉两次减法代码里也少写点括号。这个“全集减去重复计数的交叉项”的思维方式其实在很多计数题里都出现。它本质上是容斥原理最简单的两个集合版本。理解了它以后遇到“统计满足条件 A 或条件 B 的对象数”这类问题时会自然想到|A| |B| - |A∩B|。4. 代码、复杂度与“耗时100内存98”是怎么来的4.1 主推 C 实现只需十几行核心思路落实成代码非常短。我主要用 C 写给出完整可运行版本class Solution { public: int oddCells(int m, int n, vectorvectorint indices) { vectorint rowCount(m, 0), colCount(n, 0); // 第一轮只统计每个行、列被操作了多少次 for (auto idx : indices) { rowCount[idx[0]] ^ 1; // 用异或记录奇偶性等价于每次操作后取反 colCount[idx[1]] ^ 1; } int oddRows 0, oddCols 0; for (int x : rowCount) oddRows x; for (int x : colCount) oddCols x; return oddRows * n oddCols * m - 2 * oddRows * oddCols; } };这里有一个很多人会问的点为什么用^ 1而不是再取模因为我们对每个行、列只关心它最终被操作的次数是奇数还是偶数。异或 1 的作用等价于如果原来是 0 变成 1如果原来是 1 变成 0。操作两次的行先 0 变 1再 1 变 0自动抵消。这不仅让代码更短语义上也更贴近“只需要奇偶性”的需求。如果你觉得异或不够直观完全可以写成rowCount[idx[0]]最后统计时x % 2。但^ 1的写法能帮你建立“奇偶状态翻转”的直觉后文扩展部分还会用到。4.2 我的三次提交对比从暴力到公式解我第一次提交就是暴力模拟开一个二维矩阵跑完再双层循环数奇数。当时结果大概是耗时 64%内存 31%。能过但看到那个排名心里挺别扭的。第二次我改成行列数组统计但最后仍然选择“重建一个虚拟矩阵”或者“双重循环遍历所有格子”用rowCount[i] colCount[j]判断是否奇数。这一版时间立刻上去了到 80% 多内存也到了 80% 左右。第三次也就是最终版本把最后一步换成了公式不遍历格子直接拿oddRows、oddCols算答案。这样连 m*n 的扫描都省了时间来到 100%内存排到 98%。三次对比能清楚看到优化的阶梯第一次的瓶颈在空间建了二维矩阵即使题目限制下内存不大相对排名也低第二次的瓶颈在最后一步虽然只用一维数组但最后判断奇数格子时仍然做了 O(mn) 的遍历第三次彻底跳出“枚举格子”的思路用数学把格子数量直接算出来时间复杂度只剩 O(L m n)这也解释了为什么最终版能同时拿到“耗时 100、内存 98”。耗时 100 是因为整个算法没有任何冗余循环内存 98 是因为只开了两个长度不超过 50 的vectorint连一个vectorbool都不用开。LeetCode 的百分比受提交环境影响会有波动不同时间提交可能差几个点但“跑在最优档”这个判断是稳的。4.3 两种变体取模计数 vs 异或打标记除了主推版本还有两种常见写法。我实际评测下来它们的时间和内存基本一样选哪种主要看个人风格。第一种是计数取模版class Solution { public: int oddCells(int m, int n, vectorvectorint indices) { vectorint rows(m), cols(n); for (auto e : indices) { rows[e[0]]; cols[e[1]]; } int oddRows 0, oddCols 0; for (int x : rows) oddRows (x 1); for (int x : cols) oddCols (x 1); return oddRows * n oddCols * m - 2 * oddRows * oddCols; } };第二种是把行列数组都换成vectorboolclass Solution { public: int oddCells(int m, int n, vectorvectorint indices) { vectorbool rows(m, false), cols(n, false); for (auto e : indices) { rows[e[0]] !rows[e[0]]; cols[e[1]] !cols[e[1]]; } int oddRows 0, oddCols 0; for (bool x : rows) oddRows x; for (bool x : cols) oddCols x; return oddRows * n oddCols * m - 2 * oddRows * oddCols; } };vectorbool是特化的每个元素只占 1 个 bit所以在 m、n 到 1e5 的场景下它会比vectorint节省非常多内存。不过本题 m、n 最大只有 50两种差别不大。我在这里提到它是为了给后面扩展方向做铺垫。5. 边界情况、易错点和面试追问方向5.1 indices 为空、重复操作、大数溢出先说最基础的边界情况。如果indices长度为 0那rowCount、colCount全为零oddRows、oddCols也都是 0公式返回 0。这一步不用特判公式天然成立。这正好说明“不要一上来就写一堆 if 判断边界”的价值把逻辑化简到公式层面后很多边界会自动消失。重复操作也是个有趣的场景。假设某个行在indices里出现了两次那它总共被操作两次最终对答案的贡献是 0因为偶数次操作不改变奇偶性。在暴力模拟里这 2 次操作会实打实地给这行的每个格子加 2在公式解法里^ 1让状态翻转两次又回到 0。这是“只需关注奇偶性”带来的天然抗冗余能力。溢出问题在本题完全不存在因为 m、n 最多 50oddRows * n最大是 50 * 50 2500int 远够。但如果是变种题m、n 放大到 1e5oddRows * n就能到 1e10那时候必须用long long而不是int。我建议日常刷题无论题目范围大小涉及乘法求数量的统一用long long写返回值或中间变量省得哪次改数据范围时踩坑。5.2 如果操作次数变成 1e9怎么继续优化我刷题时习惯性会追问如果原题条件变了我的解法还能不能撑住比如 m、n 不变但indices长度变成 1e9显然 O(L) 都过不去。这时可以用“压缩映射”的思路因为行、列只关注奇偶性同一个行出现 2 次等于没出现。所以可以遍历indices用一个哈希表或者布尔数组记录每个行、列当前奇偶状态。如果目标是大数据流场景可以对行坐标和列坐标分别去重只保留出现次数为奇数的那些。这样哪怕 L 巨大只要不同的行、列数量有限就能把问题规模压缩到 O(mn) 或者 O(去重后的数量)。更进一步因为本题 m、n 不超过 50可以不用数组直接用两个 64 位整数当位掩码用。每一位代表一行或一列的奇偶状态class Solution { public: int oddCells(int m, int n, vectorvectorint indices) { long long rowMask 0, colMask 0; for (auto e : indices) { rowMask ^ (1LL e[0]); colMask ^ (1LL e[1]); } int oddRows __builtin_popcountll(rowMask); int oddCols __builtin_popcountll(colMask); return oddRows * n oddCols * m - 2 * oddRows * oddCols; } };这个写法很酷但实用性略低于可读性。我把它放在这里更多是作为“位运算 奇偶性”的小彩蛋。真要面试时写出这种版本记得主动解释__builtin_popcountll是 GCC 内建的统计二进制 1 个数的函数不然面试官可能会愣一下。5.3 换个问法要求输出奇数格子的坐标怎么办还有一种衍生问法不只要数量还要把所有奇数格子的坐标打印出来。这时候公式只能给出总数不能直接给出坐标列表因为坐标本身是离散的必须逐一枚举。但思路依然可以复用。你已经知道了哪些行是奇数行、哪些列是奇数列也知道奇数格子只出现在“奇数行 偶数列”和“偶数行 奇数列”两类位置。打印坐标时只需要遍历奇数行和所有偶数列输出(i, j)遍历偶数行和所有奇数列输出(i, j)这样就不需要模拟整个矩阵再全量扫描比暴力解法还是干净很多。输出规模的复杂度下限是 O(ans)无论如何跑不掉但避免了维护二维数组的开销。这类“告诉你能不能少做无用功”的题核心其实都是同一点先思考答案受哪些独立维度影响再想办法把维度解耦。LeetCode 1252 的行和列就是两个几乎完全独立的维度唯一需要小心的只是交叉点的奇偶叠加。最后分享一个我在重刷这题时的实际体会拿到一道题先忍住“立刻写第一个能过的版本”的冲动多花两分钟追问一句“有没有办法不把矩阵建出来”。这道 Easy 题如果只满足于模拟你可能永远意识不到可以用一个公式收尾。刷题积累的不应该是题号而是这种从“模拟”走向“推导”的思维方式。下次再看到带“操作计数”的矩阵题建议你先画一下行和列的影响范围再决定要不要真的动那个矩阵。