企业官网建设流程全解析

LeetCode-Go 题解：1738. Find Kth Largest XOR Coordinate Value（二维异或前缀和 + 第 K 大取值）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 1738 题《Find Kth Largest XOR Coordinate Value》展开，结合 LeetCode-Go 仓库中该题的 README 题解文档 与 Go 源码实现，系统讲解"二维异或前缀和"的推导过程、两种空间复杂度的 Go 实现（二维前缀和版与 O(n) 空间压缩版），以及求第 K 大值的排序、优先队列、partition 三种策略的取舍。读完本文，你将掌握异或运算与二维前缀和结合的推导技巧、按行滚动生成前缀和的空间优化思路，并能直接运行仓库测试验证两种解法。

题目回顾：矩阵坐标值的定义

题目给出一个大小为m x n、元素为非负整数的二维矩阵matrix与整数k，要求求出所有坐标值中第k大的值（k从 1 开始计数）。

坐标(a, b)的"值"定义如下：对满足0 <= i <= a < m且0 <= j <= b < n的所有元素matrix[i][j]（下标从 0 开始）执行异或（XOR）运算得到的结果。也就是说，(a, b)的值等于以(0, 0)为左上角、(a, b)为右下角的矩形子区域中全部元素的异或和。

题目的核心约束（来自 README.md）：

由于矩阵最大可达1000 x 1000，坐标总数为m * n（最大 100 万个）。如果对每个坐标都暴力遍历其矩形区域求异或和，复杂度会达到O(m²·n²)，在最大规模下不可接受，因此需要前缀和思想把单次区域查询降到O(1)。

官方示例拆解

README 给出了 4 个示例，矩阵均为matrix = [[5,2],[1,6]]：

注意示例 4 揭示了异或前缀和与普通求和前缀和的关键差异：5 XOR 2 XOR 1 XOR 6 = 0，即整块 2x2 区域的异或结果为 0。这是由异或运算的"自反性"（x ^ x = 0）导致的——四个数恰好两两配对抵消。理解这一点是后面推导递推式的核心。

核心思路一：区间异或与二维前缀和的类比

题目要求计算任意(0,0)到(a,b)矩形区域的异或和，这与"区间求和"问题中二维前缀和解决(0,0)到(a,b)矩形区域求和是同一类结构，区别仅在于把"加法"换成"异或"。

设preSum[i][j]表示以(0,0)为左上角、(i,j)为右下角的矩形区域内全部元素的异或和，即：

preSum[i][j] = matrix[0][0] ^ ... ^ matrix[i][j]（整个 (0,0)-(i,j) 矩形区域）

二维异或前缀和与普通二维求和前缀和完全同构：由于异或满足交换律、结合律，且任意元素出现两次即抵消（x ^ x = 0），我们可以直接套用二维前缀和的容斥式：

preSum[i][j] = preSum[i-1][j] ^ preSum[i][j-1] ^ preSum[i-1][j-1] ^ matrix[i][j]

递推式的推理过程

以(i,j)为右下角的矩形区域，可以看作由三部分拼接而成：

1. 上半部分：以(i-1,j)为右下角的矩形（覆盖0..i-1行、0..j列）；
2. 左半部分：以(i,j-1)为右下角的矩形（覆盖0..i行、0..j-1列）；
3. 当前元素matrix[i][j]。

当对这三部分做异或时，左上角的重叠区域(0,0)-(i-1,j-1)在preSum[i-1][j]与preSum[i][j-1]中各出现一次，恰好异或抵消为 0（这正是x ^ x = 0性质的体现），因此需要再补异或一次preSum[i-1][j-1]，最终得到上面的递推式。

用边界情况验证：preSum[0][0] = matrix[0][0]；对于第一行preSum[0][j] = preSum[0][j-1] ^ matrix[0][j]，即行内前缀异或；对于第一列同理。所有值都与题目的"坐标值"定义一一对应，preSum[i][j]就是坐标(i,j)的值。

解法二：二维前缀和数组版

对应 README 中的"解法二"，也是递推式最直接的落地实现，源码见 1738. Find Kth Largest XOR Coordinate Value.go：

// 解法二 前缀和 func kthLargestValue1(matrix [][]int, k int) int { nums, prefixSum := []int{}, make([][]int, len(matrix)+1) prefixSum[0] = make([]int, len(matrix[0])+1) for i, row := range matrix { prefixSum[i+1] = make([]int, len(matrix[0])+1) for j, val := range row { prefixSum[i+1][j+1] = prefixSum[i+1][j] ^ prefixSum[i][j+1] ^ prefixSum[i][j] ^ val nums = append(nums, prefixSum[i+1][j+1]) } } sort.Ints(nums) return nums[len(nums)-k] }

实现细节说明：

• prefixSum的维度是(m+1) x (n+1)，多出的一行一列全部为零。这样递推式中的prefixSum[i][j]对应(i-1,j-1)坐标，第一行、第一列在递推时天然与 0 异或（x ^ 0 = x），无需单独处理边界，这正是代码中prefixSum[i+1][j+1] = prefixSum[i+1][j] ^ prefixSum[i][j+1] ^ prefixSum[i][j] ^ val对应递推式preSum[i][j] = preSum[i-1][j] ^ preSum[i][j-1] ^ preSum[i-1][j-1] ^ matrix[i][j]的原因；
• 每算出一个prefixSum[i+1][j+1]就追加到nums，最终nums收集了全部m * n个坐标值；
• 对nums升序排序后，第k大（1-indexed）的元素位于nums[len(nums)-k]。

时间复杂度为O(m·n + (m·n)·log(m·n))（遍历矩阵 + 排序），空间复杂度为O(m·n)（前缀和数组 + 结果切片）。

核心思路二：O(n) 空间压缩的按行滚动前缀和

README 指出：上面的解法用二维数组保存前缀和，空间复杂度为O(m·n)。仔细观察递推式可以发现，preSum的每一行只依赖当前行的左邻居preSum[i][j-1]与上一行的同列值preSum[i-1][j]、preSum[i-1][j-1]。因此前缀和可以"一行一行"地生成：先生成第i-1行的前缀和，生成第i行时，异或计算完成后可以用新值覆盖旧值，对后续计算没有影响。这与滚动数组优化 DP 空间复杂度是完全一致的思路，也是 README 中"压缩版前缀和"的核心。

解法一：压缩版前缀和

对应 README 中的"解法一"，源码见 1738. Find Kth Largest XOR Coordinate Value.go：

// 解法一 压缩版的前缀和 func kthLargestValue(matrix [][]int, k int) int { if len(matrix) == 0 || len(matrix[0]) == 0 { return 0 } res, prefixSum := make([]int, 0, len(matrix)*len(matrix[0])), make([]int, len(matrix[0])) for i := range matrix { line := 0 for j, v := range matrix[i] { line ^= v prefixSum[j] ^= line res = append(res, prefixSum[j]) } } sort.Ints(res) return res[len(res)-k] }

这段代码虽然只有十余行，但将"滚动前缀和"用到了极致，拆解如下：

1. line（行内前缀异或）：line ^= v累加当前行0..j列的前缀异或，即一维前缀和preSum[i][0..j]的"横向部分"；
2. prefixSum[j]（纵向累积）：prefixSum[j] ^= line等价于"上一行同一列的值 XOR 当前行行内前缀"，即在原位置完成preSum[i][j] = preSum[i-1][j] ^ (matrix[i][0] ^ ... ^ matrix[i][j])的覆盖更新；
3. res预分配容量：make([]int, 0, len(matrix)*len(matrix[0]))预分配m*n容量，避免 append 过程中的多次扩容，减少内存分配开销；
4. 边界防御：开头if len(matrix) == 0 || len(matrix[0]) == 0处理空矩阵/空行，直接返回 0。

为什么能覆盖原数据？因为在计算preSum[i][j]时，prefixSum[j]里存的还是preSum[i-1][j]（上一行的值），只需要再异或上当前行的横向前缀line，就得到preSum[i][j]。计算完成后立即覆盖，而后续列的计算只用到"当前行"的左邻居（通过line携带）和"当前列"的最新值，上一行的旧值已无引用，覆盖是安全的。这样空间从O(m·n)降为O(n)。

时间复杂度仍为O(m·n + (m·n)·log(m·n))，空间复杂度降为O(n + m·n)（prefixSum数组为O(n)，结果切片仍需保存全部m*n个值）。

两种解法对比

README 也特别点明：压缩空间的方法与优化 DP 空间复杂度是同一思路，若熟悉滚动数组，解法一的代码将很容易读懂。

核心思路三：如何高效取出第 K 大的值

算出全部m·n个坐标值后，问题退化为"从无序数组中找第 k 大元素"。README 明确指出有三种做法：

1. 排序：对全部值升序排序，取res[len(res)-k]；
2. 优先队列（堆）：维护大小为k的最小堆，堆顶即为第 k 大，复杂度O(n·log k)；
3. partition（快速选择）：即 0215. Kth Largest Element in an Array 一题中的O(n)期望复杂度的 partition 方法，理论基础是 partition 后基准值所在下标即为其最终排序位置，据此判断第 k 大的元素落在哪一侧。

README 给出了一个重要的工程化结论：理论上 O(n) 的 partition 时间复杂度最低，但经过实际测试，runtime 最优的反而是排序方法。因此仓库中两种解法均采用了sort.Ints排序方案。从 215. Kth Largest Element in an Array.go 的源码也可以看到同样的经验：该题也同时实现了排序（findKthLargest1）与随机化 partition（findKthLargest+selectSmallest+partition）两种解法，注释同样写道"排序的方法反而速度是最快的"。原因在于 Go 标准库sort.Ints使用 pdqsort 等高度优化的混合排序，常数因子极小，而 partition 方法带有随机化开销且最坏情况退化为O(n²)，在 LeetCode 实测环境下排序反而更优。

排序取第 K 大的一行代码

sort.Ints(res) return res[len(res)-k]

由于res升序排列，第 1 大是最后一个元素res[len(res)-1]，第k大对应res[len(res)-k]，与题目"k 从 1 开始计数"的要求完全一致。

测试验证：100% 覆盖率的表驱动用例

仓库为该题提供了完整的测试文件 1738. Find Kth Largest XOR Coordinate Value_test.go，采用表驱动测试风格：

• 定义question1738结构体组合参数para1738（matrix、k）与期望答案ans1738（one）；
• 覆盖 README 中的全部 4 个官方示例（k = 1/2/3/4，期望值分别为7/5/4/0），并逐一调用两种解法验证；
• 额外覆盖空矩阵[][]int{}与空行[][]int{{}}两个边界分支，断言kthLargestValue返回 0，确保解法一的判空防御分支被测试覆盖。

这也呼应了项目描述中"100% test coverage"的工程实践。运行方式：在仓库根目录执行go test ./leetcode/...，或参考 gotest.sh 中的覆盖率统计方式（go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...）。

从测试可见，仓库遵循一致的题解约定：每个题目目录包含题解源码（*.go）、同名测试（*_test.go）与 README 说明，源码中同时保留两种解法（kthLargestValue与kthLargestValue1），分别对应"压缩版前缀和"与"二维前缀和"两条思路，方便读者对照学习。

小结

• 本体的数学本质是二维前缀和的异或版本，递推式preSum[i][j] = preSum[i-1][j] ^ preSum[i][j-1] ^ preSum[i-1][j-1] ^ matrix[i][j]由异或自反性（x ^ x = 0）保证容斥项的正确性；
• 空间优化层面，利用"每行前缀和只依赖上一行"的特性，可用一维数组滚动覆盖，把前缀和空间从O(m·n)压缩到O(n)，与滚动数组优化 DP 的思路同源；
• 取值层面，排序、优先队列、partition 三种方案各有适用场景，本仓库实测推荐排序（sort.Ints+res[len(res)-k]），与 215 题的经验一致。

如需完整运行与调试，可直接查看 1738 题目录 下的源码与测试文件。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go