问题描述给定一个m x n的整数矩阵matrix该矩阵具有以下特性每行的元素从左到右按升序排列。每列的元素从上到下按升序排列。请编写一个高效的算法判断目标值target是否存在于矩阵中。示例 1输入matrix [[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算法思路从右上角出发暴力遍历整个矩阵需要 O(m * n) 的时间复杂度。利用矩阵的排序特性我们可以从矩阵的右上角或左下角开始搜索实现线性时间的查找。核心思想初始化指针在右上角(row0, coln-1)。将当前指针指向的值cur与目标值target比较如果cur target查找成功返回true。如果cur target说明当前值太大而同一列下方的值都更大因此不可能在当前列找到目标。将指针向左移动一列(col--)。如果cur target说明当前值太小而同一行左边的值都更小因此不可能在当前行找到目标。将指针向下移动一行(row)。重复步骤2直到找到目标或指针移出矩阵边界row m或col 0。若移出边界则说明矩阵中不存在目标值返回false。这种方法每一步都排除掉一行或一列因此最多走m n步时间复杂度为O(m n)空间复杂度为O(1)。代码实现以下是该算法的 Java 实现classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){intmmatrix.length;intnmatrix[0].length;// 从右上角开始introw0;intcoln-1;while(rowmcol0){intcurmatrix[row][col];// 找到了if(curtarget){returntrue;}// 当前值太大往左走elseif(curtarget){col--;}// 当前值太小往下走else{row;}}returnfalse;}}图解算法流程为了更直观地理解搜索路径下图展示了在一个 5x5 矩阵中查找目标值5的过程。指针从右上角(0,4)开始根据比较结果逐步向左或向下移动最终在(1,1)位置找到目标。(上图展示了从右上角开始的搜索路径红色箭头表示移动方向绿色单元格表示找到目标)复杂度分析时间复杂度O(m n)。最坏情况下指针从右上角移动到左下角总共移动m n步。空间复杂度O(1)。只使用了几个整型变量。总结从右上角或左下角开始的“步进法”是解决此类行列均有序矩阵搜索问题的经典且高效的方法。它巧妙地利用了排序特性每次比较都能排除一整行或一整列将搜索复杂度从二次降为线性。掌握这种思路对于解决类似的二维搜索问题大有裨益。在后续章节中我们可以探讨此算法的变种、与其他解法如二分查找的比较以及在实际项目中的应用场景。