教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文基于 LogicStack-LeetCode 仓库中的 1738. 找出第 K 大的异或坐标值中等题解 展开系统讲解「二维前缀异或」与「Top K 堆」两大核心技术。读完本文你将掌握如何利用异或的容斥特性在 O(1) 时间内求出任意左上角为 (0,0) 的子矩阵异或和并用大小为 k 的小根堆在 O(m·n·log k) 内定位第 k 大值同时理解一维前缀异或1310、二维前缀和304与 Top K 堆215、703之间的知识脉络。一、题目回顾什么是异或坐标值这是 LeetCode 上的1738. 找出第 K 大的异或坐标值难度为中等题目标签为「Top K」、「数学」、「前缀和」。题目描述给你一个二维矩阵matrix和一个整数k矩阵大小为m x n由非负整数组成。矩阵中坐标(a, b)的值定义为对所有满足0 i a m且0 j b n的元素matrix[i][j]下标从 0 开始计数执行异或运算得到的结果。请你找出matrix的所有坐标中第k大的值k从 1 开始计数。换句话说每个坐标(a, b)都对应一个以 (0,0) 为左上角、(a,b) 为右下角的子矩阵异或和本题要求在这m × n个异或和中找出第k大的那个。示例与解释原题给出四个示例使用同一个矩阵matrix [[5,2],[1,6]]示例k输出计算过程示例 117坐标 (0,1) 的值是5 XOR 2 7为最大的值示例 225坐标 (0,0) 的值是5为第 2 大的值示例 334坐标 (1,0) 的值是5 XOR 1 4为第 3 大的值示例 440坐标 (1,1) 的值是5 XOR 2 XOR 1 XOR 6 0为第 4 大的值提示数据范围约束m matrix.lengthn matrix[i].length1 m, n 10000 matrix[i][j] 10^61 k m * n二、基本分析从朴素枚举到可优化的计算模型根据题意这道题本质上是求所有子矩阵中第 k 大的异或和同时规定所有子矩阵的左上角端点恒为(0, 0)。数据范围为10^3即 m、n 最大均为 1000因此「枚举所有右下角」并「每次计算子矩阵异或和」的朴素做法复杂度为 $O(m^2 \times n^2)$在极限数据约 $10^{12}$ 次运算下完全不可行无需考虑。关键观察要在全局中找最优解「枚举所有右下角」这一过程不可避免共有 $m \times n$ 个坐标我们唯一能优化的环节是每次计算子矩阵异或和的过程。这个分析过程与仓库中的 1310. 子数组异或查询 一脉相承——那道题解决的是一维区间异或的 O(1) 查询而本题将其推广到二维。核心思想异或是不进位加法可以利用「偶数次异或结果为 0」的特性实现类似「前缀和」的容斥。这使得我们可以在 O(1) 的复杂度内计算某个子矩阵的异或和。三、原理铺垫一维前缀异或的容斥本质在进入二维之前先回顾一维情况。在 1310. 子数组异或查询 中原文档明确指出本题主要利用异或运算中的「相同数值进行运算结果为 0」的特性。对于特定数组 $[a_1, a_2, a_3, ..., a_n]$要求得任意区间 $[l, r]$ 的异或结果可以通过 $[1, r]$ 和 $[1, l-1]$ 的异或结果得出 $$ xor(l, r) xor(1, r) \oplus xor(1, l-1) $$本质上还是利用集合区间结果的容斥原理。只不过前缀和需要利用「减法逆运算」做容斥而前缀异或是利用「相同数值进行异或结果为 0偶数次的异或结果为 0」的特性实现容斥。一维前缀异或的构建方式为// sum[i] 表示 arr[0..i-1] 的异或和 for (int i 1; i n; i) sum[i] sum[i - 1] ^ arr[i - 1]; // 查询 [l, r]0 基下标的异或和 ans sum[r 1] ^ sum[l];正是因为x ^ x 0重复出现的公共前缀部分会在异或中自动抵消这就是异或版容斥能够成立的根本原因。四、二维前缀异或递推公式与推导4.1 递推公式创建二维数组sum[][]令sum[i][j]为以(i, j)为右下角、(0, 0)为左上角的子矩阵异或和可得计算公式$$ sum[i][j] sum[i-1][j] \oplus sum[i][j-1] \oplus sum[i-1][j-1] \oplus matrix[i-1][j-1] $$4.2 为什么是异或版容斥这一点与仓库中 304. 二维区域和检索 - 矩阵不可变 的二维前缀和公式形式完全一致只是把「加减」换成「异或」前缀和版本sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] matrix[i-1][j-1]304 题解中的核心模板前缀异或版本sum[i][j] sum[i-1][j] ^ sum[i][j-1] ^ sum[i-1][j-1] ^ matrix[i-1][j-1]二者的几何含义相同sum[i-1][j]覆盖了上方的矩形区域sum[i][j-1]覆盖了左侧的矩形区域两者叠加时左上角sum[i-1][j-1]对应的区域被计算了两次在加法模型中用「减去一次」来抵消在异或模型中由于「偶数次异或结果为 0」自动抵消。最后再异或上当前格子的值matrix[i-1][j-1]。注意前缀数组sum的尺寸为(m1) × (n1)下标从 1 开始这样i1或j1时sum[i-1][j]、sum[i][j-1]、sum[i-1][j-1]均自然为 0无需单独处理边界这是与一维前缀和下标从 1 开始相同的模板惯例参见 304 题解 中的模板说明。五、Top K 问题为什么选择大小为 k 的小根堆计算完所有m × n个子矩阵异或和之后剩下的问题变成如何从所有「子矩阵异或和」中找到第 k 大的值。这转化为了经典的 Top K 问题可以使用「排序」或「堆」进行求解。5.1 维护大小为 k 的小根堆具体的我们可以建立一个大小为k的小根堆Java 中用PriorityQueue实现在计算二维前缀异或的同时判断当前「子矩阵异或和」是否大于堆顶元素大于堆顶元素当前子矩阵异或和可能是第 k 大的值而堆顶元素堆中最小的那个不可能成为第 k 大的值将堆顶元素弹出并将当前子矩阵和加入堆中小于堆顶元素不会是第 k 大的值直接丢弃等于堆顶元素堆中已有相同元素直接丢弃保持堆内元素互不重复计数避免重复值干扰第 k 大判定。当所有坐标遍历完毕堆中恰好保存了全部异或和中最大的 k 个值堆顶最小值即为第 k 大的答案。5.2 正确性直观解释小根堆的特性是堆顶永远是最小值。当堆满 k 个元素后任何小于堆顶的新值都不可能进入前 k 大只有大于堆顶的值才会替换掉当前的前 k 大中最小的那个。算法结束时堆内恰好是前 k 大堆顶就是第 k 大。这与仓库 Index/堆.md 中收录的 215. 数组中的第K个最大元素、703. 数据流中的第 K 大元素 等 Top K 系列题目采用完全相同的堆思路。六、完整代码实现6.1 Java 实现原文档代码class Solution { public int kthLargestValue(int[][] mat, int k) { int m mat.length, n mat[0].length; int[][] sum new int[m 1][n 1]; PriorityQueueInteger q new PriorityQueue(k, (a, b)-a - b); for (int i 1; i m; i) { for (int j 1; j n; j) { sum[i][j] sum[i - 1][j] ^ sum[i][j - 1] ^ sum[i - 1][j - 1] ^ mat[i - 1][j - 1]; if (q.size() k) { q.add(sum[i][j]); } else { if (sum[i][j] q.peek()) { q.poll(); q.add(sum[i][j]); } } } } return q.peek(); } }代码要点解读sum数组开成(m1) × (n1)下标 1 基化天然规避边界特判PriorityQueue(k, (a, b) - a - b)创建容量为 k 的小根堆默认即升序堆顶是最小值二维前缀异或计算与 Top K 维护合并在同一个双重循环中完成一次遍历同时拿到所有异或和与第 k 大无需额外存储全部结果空间上只付出O(m·n)的前缀数组代价前 k 个元素直接入堆堆未满时不比较第 k1 个起才与堆顶比较决定去留。6.2 Python 实现便于本地调试的等价改写根据上述完全相同的算法逻辑可直接改写为 Python堆使用heapq注意 Python 的heapq默认是小根堆import heapq class Solution: def kthLargestValue(self, matrix: List[List[int]], k: int) - int: m, n len(matrix), len(matrix[0]) s [[0] * (n 1) for _ in range(m 1)] heap [] for i in range(1, m 1): for j in range(1, n 1): s[i][j] s[i - 1][j] ^ s[i][j - 1] ^ s[i - 1][j - 1] ^ matrix[i - 1][j - 1] if len(heap) k: heapq.heappush(heap, s[i][j]) elif s[i][j] heap[0]: heapq.heapreplace(heap, s[i][j]) return heap[0]6.3 C 实现等价改写class Solution { public: int kthLargestValue(vectorvectorint mat, int k) { int m mat.size(), n mat[0].size(); vectorvectorint sum(m 1, vectorint(n 1, 0)); priority_queueint, vectorint, greaterint q; // 小根堆 for (int i 1; i m; i) { for (int j 1; j n; j) { sum[i][j] sum[i - 1][j] ^ sum[i][j - 1] ^ sum[i - 1][j - 1] ^ mat[i - 1][j - 1]; if (q.size() k) { q.push(sum[i][j]); } else if (sum[i][j] q.top()) { q.pop(); q.push(sum[i][j]); } } } return q.top(); } };七、复杂度分析时间复杂度$O(m \times n \times \log{k})$。二维前缀异或的计算为 $O(1)$ 每次共 $m \times n$ 个坐标每次堆的插入/弹出操作代价为 $O(\log{k})$整体即 $O(m \times n \times \log{k})$。空间复杂度$O(m \times n)$。sum前缀数组占用(m1) × (n1)空间堆最多容纳 k 个元素$k \le m \times n$被前缀数组的空间量级覆盖。在极限数据$m n 1000$下运算规模约为 $10^6 \times \log{k} \le 10^6 \times 20 \approx 2 \times 10^7$完全可接受对比朴素的 $O(m^2 n^2) \approx 10^{12}$优化幅度是数量级的。八、用示例手推验证以matrix [[5,2],[1,6]]m2, n2为例走一遍算法sum[1][1] 0 ^ 0 ^ 0 ^ 5 5坐标 (0,0)值 5sum[1][2] 0 ^ 5 ^ 0 ^ 2 7坐标 (0,1)值 5^27sum[2][1] 5 ^ 0 ^ 0 ^ 1 4坐标 (1,0)值 5^14sum[2][2] 4 ^ 7 ^ 5 ^ 6 0坐标 (1,1)值 5^2^1^60全部异或和为{5, 7, 4, 0}降序排列为7, 5, 4, 0分别对应 k1、2、3、4 的答案与原文档四个示例完全吻合。这验证了二维前缀异或递推公式与堆维护逻辑的正确性。九、知识脉络与延伸阅读本题处于前缀和/容斥与Top K/堆两大知识板块的交汇处仓库 Index 目录 中提供了完备的索引体系可配合阅读Index/前缀和.md收录 1310一维前缀异或、304二维前缀和、1074子矩阵计数、1744、1838 等一维/二维前缀和系列题解本题即其中 1738 条目的原题题解Index/容斥原理.md从集合容斥视角收录 304、1310、1442 等题目帮助理解前缀和用减法、前缀异或用偶次异或归零的统一原理Index/堆.md收录 215数组中第 K 个最大元素、703数据流中的第 K 大元素、295数据流中位数、264丑数 II等 Top K/优先队列题解与本题大小为 k 的小根堆思路完全同源Index/数学.md收录 1734解码异或后的排列、1486数组异或操作、810黑板异或游戏等异或运算相关题目可深化对异或代数性质的理解。推荐的进阶学习路径先刷 1310. 子数组异或查询掌握一维前缀异或与区间容斥再刷 304. 二维区域和检索 - 矩阵不可变吃透二维前缀和模板加法版容斥最后回归本题 1738将二维前缀和与前缀异或融合配合 215、703 的 Top K 堆模板即可完整掌握此类矩阵子区域统计 Top K综合题的通解。十、小结1738 题是一道非常典型的数据结构叠加中等题考察点可拆解为三层数学层理解异或偶次归零的容斥特性这是前缀异或可行的根基前缀层将一维前缀异或推广到二维用 $O(mn)$ 预处理换取每次子矩阵异或和的 $O(1)$ 查询Top K 层在遍历的同时用大小为 k 的小根堆在线维护前 k 大最终堆顶即为第 k 大的答案。三者叠加最终以 $O(mn\log k)$ 的时间、$O(mn)$ 的空间优雅收尾。掌握本题的推导链条等于同时掌握了一维/二维前缀和异或容斥Top K 堆三组高频考点遇到类似的矩阵区域统计 极值查询类题目时即可举一反三。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐raylib 环境一次跑通从装库到窗口弹出的最短路径与排错手册raylib 环境一次跑通从装库到窗口弹出的最短路径与排错手册 raylib 是一个用 C 语言写的游戏开发库窗口、2D/3D 图形、纹理、模型、音频这些底游戏开发图形学3D渲染LogicStack-LeetCode 前缀和专题实战从一维区间求和到二维矩阵、异或与哈希变种LogicStack LeetCode 前缀和专题实战从一维区间求和到二维矩阵、异或与哈希变种 LogicStack LeetCode 是公众号「宫水三叶的刷教程文档KernelSU GKI 与 LKM 模式怎么选5 步完成内核 Root不再卡在刷机上KernelSU GKI 与 LKM 模式怎么选5 步完成内核 Root不再卡在刷机上 KernelSU 是跑在内核里的 Android root 方案直教程文档上一篇Python-Markdown扩展大全18个官方扩展功能详解下一篇终极PEX开发工作流使用uv和dev-cmd提升Python项目效率的完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考