LeetCode-Go 题解 240Search a 2D Matrix II 二维矩阵高效搜索O(mn) 与二分两种 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 240 题「Search a 2D Matrix II」展开核心解决一个实战高频问题在行、列分别升序但整体并非一维有序的 m×n 矩阵中如何高效判断某个目标值是否存在。你将掌握两种经典思路——从右上角出发的线性扫描O(mn)与逐行二分O(n log n)并看到它们在 LeetCode-Go 仓库中的完整 Go 实现与单测用例可直接复制运行或改造到自己的工程中。题目描述编写一个高效算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下两个特性每行的元素从左到右升序排列每列的元素从上到下升序排列。例如考虑如下矩阵[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]给定 target 5返回true给定 target 20返回false。题目大意编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性每行的元素从左到右升序排列每列的元素从上到下升序排列。矩阵结构分析为什么不能直接当成一维数组二分这是本题与 74. Search a 2D Matrix 的本质区别。第 74 题中的矩阵具备上一行末尾元素小于下一行开头元素的额外约束因此可以按行序拍扁成一个完整有序的一维数组直接对整个矩阵做一次二分搜索仓库实现见 74. Search a 2D Matrix.go通过matrix[mid/m][mid%m]完成行列坐标换算。而本题只保证每行内部、每列内部分别有序相邻两行之间并没有大小关系。例如上例中第一行最后一个元素15就比第二行第一个元素2大整个矩阵拍扁后并不单调。因此 74 题的整体二分思路在这里不成立需要重新利用矩阵的局部有序性设计搜索策略。解法一从右上角出发的线性扫描O(mn)核心思路观察矩阵可以发现最右边一列的元素是本行中最大的元素。于是可以从矩阵的右上角第 0 行、最后一列出发把该位置当作决策点若target matrix[row][col]直接命中若target matrix[row][col]说明 target 比本行所有元素都大向下移动一行row排除整行若target matrix[row][col]说明 target 比本列所有元素都小向左移动一列col--排除整列。每一次比较都能安全地排除掉一整行或一整列最多走 m n 步就会越界结束因此时间复杂度为 O(mn)。这也是 README 中提到的模拟解法先利用最右列快速定位再在行内向左收窄。仓库源码实现仓库中的searchMatrix240即该思路的完整实现见 240. Search a 2D Matrix II.go// 解法一 模拟时间复杂度 O(mn) func searchMatrix240(matrix [][]int, target int) bool { if len(matrix) 0 { return false } row, col : 0, len(matrix[0])-1 for col 0 row len(matrix)-1 { if target matrix[row][col] { return true } else if target matrix[row][col] { row } else { col-- } } return false }几个实现细节值得注意空矩阵保护len(matrix) 0时直接返回false避免访问matrix[0]造成 panic初始位置row 0、col len(matrix[0])-1即右上角循环边界col 0 row len(matrix)-1越界即意味着矩阵中不存在 target排除方向target matrix[row][col]时row排除当前行否则col--排除当前列。直观推演以 target 5 为例从右上角(0, 4)即15开始5 15→ 排除最后一列col 3位置(0, 3)115 11→ 排除该列col 2位置(0, 2)75 7→ 排除该列col 1位置(0, 1)45 4→ 排除第 0 行row 1位置(1, 1)55 5→ 返回true。整个过程只访问了 5 个元素远小于 25 个元素的暴力遍历。解法二逐行二分搜索O(n log n)核心思路由于每行内部是升序的可以依次对每一行执行一次标准二分搜索。若某一行命中则返回true所有行都未命中则返回false。共有 n 行假设 n 为列数、每行二分代价为 O(log n)总复杂度为 O(n log n)。README 中将其描述为在每一行或每一列中利用二分去搜索的方案。仓库源码实现仓库中的searchMatrix2401即逐行二分的实现见 240. Search a 2D Matrix II.go// 解法二 二分搜索时间复杂度 O(n log n) func searchMatrix2401(matrix [][]int, target int) bool { if len(matrix) 0 { return false } for _, row : range matrix { low, high : 0, len(matrix[0])-1 for low high { mid : low (high-low)1 if row[mid] target { high mid - 1 } else if row[mid] target { low mid 1 } else { return true } } } return false }要点说明mid : low (high-low)1等价于(lowhigh)/2但避免了 low high 可能的整数溢出是 Go 二分搜索的推荐写法循环不变量low high时持续缩小区间high mid - 1与low mid 1保证区间严格收缩、不会死循环提前返回任意一行命中即return true无需处理后续行。当行数 m 远大于列数 n 时O(n log n) 的逐行二分可能劣于 O(mn) 的线性扫描反之若矩阵很矮胖两者差距缩小。实际工程中可根据矩阵形状权衡。与 74 题的横向对比对比维度74. Search a 2D Matrix240. Search a 2D Matrix II行内有序是是列内有序是是行间整体有序是上一行末尾 下一行开头否可拍扁成一维二分可以不可以推荐算法整体二分 O(log(m·n))右上角线性扫描 O(mn) 或逐行二分 O(n log n)仓库参考实现74. Search a 2D Matrix.go240. Search a 2D Matrix II.go一句话总结74 题靠全矩阵单调可以整体二分240 题只能利用行、列各自单调逐步排除这也是 240 题被称为 74 题加强版的原因。测试用例与运行验证仓库为本题提供了完整的 Go 单元测试见 240. Search a 2D Matrix II_test.go覆盖三组场景命中场景5x5 示例矩阵 target 5期望true未命中场景同一矩阵 target 20期望false空矩阵场景[][]int{} target 1期望false验证空矩阵保护分支。测试同时对searchMatrix240与searchMatrix2401两个实现做断言保证两种解法行为一致got : searchMatrix240(p.matrix, p.target) if got ! a.one { t.Fatalf(searchMatrix240(%v, %v) %v, want %v, p.matrix, p.target, got, a.one) } if got2 : searchMatrix2401(p.matrix, p.target); got2 ! a.one { t.Fatalf(searchMatrix2401(%v, %v) %v, want %v, p.matrix, p.target, got2, a.one) }在仓库根目录可直接运行本题测试模块名为github.com/halfrost/LeetCode-Go见 go.modgo test ./leetcode/0240.Search-a-2D-Matrix-II/ -v -run Test_Problem240若想验证整个题库的测试与覆盖率可执行仓库自带的 gotest.sh./gotest.sh该脚本会对./leetcode/...全量执行go test -covermodeatomic -coverprofilecoverage.txt生成的覆盖率文件即仓库根目录的 coverage.txt。小结解法一推荐从右上角出发利用最右列是本行最大、最上行是本列最小的性质每步排除一行或一列时间复杂度 O(mn)、空间 O(1)是本题的最优解解法二逐行二分时间复杂度 O(n log n)、空间 O(1)实现直观适合行内二分习惯边界处理两种实现都先判空矩阵再访问元素测试用例中也专门覆盖了空矩阵分支工程化时务必保留该保护。掌握利用矩阵局部有序性逐步排除搜索区域的思路后类似的行列有序矩阵搜索问题如 74 题的整体二分都可以举一反三。完整的实现与测试均可直接在 leetcode/0240.Search-a-2D-Matrix-II 目录下查阅。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考