LeetCode-Book：LCR 121「寻找目标值 - 二维数组」二叉搜索树视角的线性搜索解法详解

LeetCode-BookLCR 121「寻找目标值 - 二维数组」二叉搜索树视角的线性搜索解法详解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本文围绕《LeetCode-Book》仓库中 LCR 121. 寻找目标值 - 二维数组 一题展开讲解如何利用矩阵「从上到下递增、从左到右递增」的单调性把搜索过程等价为在一棵隐式二叉搜索树上的查找从而将暴力遍历的 $O(NM)$ 复杂度降为 $O(MN)$。读完本文你将掌握「从角落出发的消行消列搜索法」这一经典二维数组查找套路并能在 Python、Java、C 三种语言中独立写出可运行的解法同时通过仓库中同源题目的多语言实现与测试用例理解该算法在《剑指 Offer 04》与 LeetCode 240 号题之间的对应关系。题目背景与仓库中的位置「LCR 121. 寻找目标值 - 二维数组」是《剑指 Offer》中“二维数组中的查找”的力扣 LCR 版本题干把矩阵抽象为一座“仓库”的plants植物库存矩阵要求判断target是否存在于其中。该题在仓库中与以下内容同源解法文档leetbook_ioa/docs/LCR 121. 寻找目标值 - 二维数组.md《剑指 Offer》同名题文档sword_for_offer/docs/剑指 Offer 04. 二维数组中的查找.mdLeetCode 240「搜索二维矩阵 II」文档selected_coding_interview/docs/240. 搜索二维矩阵 II.md三份材料对应的解法代码分别存放在仓库的sword_for_offer/codes与selected_coding_interview/codes目录中算法思想完全一致读者可对照阅读。暴力法为何不是最优解若直接双重循环遍历整个plants矩阵时间复杂度为 $O(NM)$$N$ 为行数、$M$ 为列数。该做法完全没有利用矩阵的单调递增特性每一行从左到右递增每一列从上到下递增。暴力法的缺点在于每次只比较一个元素无法根据比较结果排除整行或整列因此最坏情况下要把矩阵中每个元素都访问一遍。显然在面试与竞赛场景下这不是最优解法正确思路是利用矩阵的结构性质做“排除法”。核心思路将矩阵视作一棵二叉搜索树文档给出了一个非常直观的模型将矩阵逆时针旋转 45°并转化为图的形式可以发现矩阵的单调结构与二叉搜索树BST完全同构——对于每个元素其“左分支”方向上的元素更小“右分支”方向上的元素更大。利用这一性质可以选取矩阵中「左下角」或「右上角」的元素作为整棵树的“根节点”开始搜索遇到比target大的元素就向“左”走消去当前行遇到比target小的元素就向“右”走消去当前列。之所以选择左下角或右上角作为起点是因为这两个位置的元素具备“一条方向递增、另一条方向递减”的特殊性从左下角出发向上行号减小元素递减向右列号增大元素递增恰好对应 BST 中“左小右大”的分支关系从而保证每轮比较都能确定性地消去一行或一列。算法流程以plants的左下角元素为起始点索引记为(i, j)从(i, j)开始遍历与target对比当plants[i][j] target时执行i--即消去第i行当plants[i][j] target时执行j即消去第j列当plants[i][j] target时返回true代表找到目标值。若行索引i 0或列索引j M发生越界则说明矩阵中不存在目标值返回false。关键不变量每轮i或j移动后相当于生成了一个“消去一行列后的新矩阵”索引(i, j)恰好指向新矩阵的左下角元素。因此可以反复套用上述性质持续消行消列直到命中目标或指针越界。该搜索过程的终止条件只有两种要么命中target要么指针越界走出矩阵边界——绝不会出现“死循环”或漏查因为每轮迭代都会严格消除一行或一列最多进行 $MN$ 次比较。多语言代码实现Pythonclass Solution: def findTargetIn2DPlants(self, plants: List[List[int]], target: int) - bool: i, j len(plants) - 1, 0 while i 0 and j len(plants[0]): if plants[i][j] target: i - 1 elif plants[i][j] target: j 1 else: return True return FalseJavaclass Solution { public boolean findTargetIn2DPlants(int[][] plants, int target) { int i plants.length - 1, j 0; while (i 0 j plants[0].length) { if (plants[i][j] target) i--; else if (plants[i][j] target) j; else return true; } return false; } }Cclass Solution { public: bool findTargetIn2DPlants(vectorvectorint plants, int target) { int i plants.size() - 1, j 0; while (i 0 j plants[0].size()) { if (plants[i][j] target) i--; else if (plants[i][j] target) j; else return true; } return false; } };三种语言的实现完全同构i从最后一行出发len(plants) - 1/plants.length - 1/plants.size() - 1j从第 0 列出发循环条件i 0 j 列数同时充当“未越界”与“未命中”的守卫循环体内按大小关系三分支处理命中即返回true循环自然结束返回false。复杂度分析时间复杂度 $O(MN)$其中 $N$ 为矩阵行数、$M$ 为矩阵列数。每轮迭代必然使i减 1 或j加 1i最多从 $N-1$ 递减到 0j最多从 0 递增到 $M-1$因此循环次数上界为 $MN$与暴力法的 $O(NM)$ 相比有显著提升。空间复杂度 $O(1)$仅使用i、j两个指针变量占用常数大小的额外空间。仓库源码印证同源三题的可运行测试用例本解法并非孤立存在仓库在同一目录树中收录了该算法的多个可运行版本代码中带完整的测试驱动Driver Code可直接编译运行验证剑指 Offer 04Pythonsword_for_offer/codes/python/sfo_04_find_a_number_in_2d_matrix_s1.py 使用测试矩阵与target 5运行后打印True剑指 Offer 04Javasword_for_offer/codes/java/sfo_04_find_a_number_in_2d_matrix_s1/sfo_04_find_a_number_in_2d_matrix_s1.java剑指 Offer 04Csword_for_offer/codes/cpp/sfo_04_find_a_number_in_2d_matrix_s1/sfo_04_find_a_number_in_2d_matrix_s1.cppLeetCode 240Javaselected_coding_interview/codes/java/lc_240_search_a_2d_matrix/lc_240_search_a_2d_matrix.javaLeetCode 240Cselected_coding_interview/codes/cpp/lc_240_search_a_2d_matrix_ii/lc_240_search_a_2d_matrix_ii_s1.cpp。各版本统一使用如下 5×5 单调矩阵作为测试用例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以 C 版本 sfo_04_find_a_number_in_2d_matrix_s1.cpp 为例其main函数构造矩阵并调用findNumberIn2DArray(matrix, 5)期望输出true。读者可以替换target的值例如改为20验证返回false的路径从而完整覆盖“命中提前返回”与“指针越界返回 false”两条分支。从源码结构可以推断仓库作者Krahets刻意保持了三个题库目录leetbook_ioa、sword_for_offer、selected_coding_interview中该题实现的一致性便于读者跨题对照学习同一核心算法。变体与易错点起点也可选右上角与左下角对称从右上角(0, M-1)出发向右j元素递增、向下i元素递减同样可行循环条件相应变为i N j 0。两种写法等价面试时可任选一种并说明理由。必须选“拐角”而非任意点只有左下角或右上角同时具备两个方向的单调性才能保证每轮确定性地排除一整行或一整列若从左上角出发两个方向都递增无法判断应该消行还是消列。越界条件的顺序循环条件必须同时检查i 0与j M两者缺一不可否则访问plants[i][j]时可能产生数组越界异常。空矩阵处理若plants为空行或列为 0初始化i -1或j 0不成立循环直接不执行并返回false天然安全无需额外判空。总结LCR 121 的核心价值在于提供了一个“化矩阵为树”的思维范式面对有序的二维结构优先寻找具备双向单调性的角落作为搜索起点利用一次比较排除整行或整列最终把二维查找化简为一条从角落到目标的最短路径。掌握这一套路后无论是 剑指 Offer 04. 二维数组中的查找 还是 240. 搜索二维矩阵 II都可以在数分钟内写出同样的最优解——这正是该题被三大题库同时收录的原因所在。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考