LeetCode 240. 搜索二维矩阵 II题目描述编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性· 每行的元素从左到右升序排列。· 每列的元素从上到下升序排列。解题思路从右上角开始搜索选择 右上角 作为起点利用矩阵的有序性进行排除· 如果当前元素等于 target返回 true。· 如果当前元素 大于 target由于当前列从上到下递增当前元素下方的所有元素都更大因此可以排除当前列向左移动一列col–。· 如果当前元素 小于 target由于当前行从左到右递增当前元素左侧的所有元素都更小因此可以排除当前行向下移动一行row。每一步都能排除一行或一列因此时间复杂度为 O(m n)。也可以从左下角开始逻辑对称。Java 实现classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){if(matrixnull||matrix.length0||matrix[0].length0){returnfalse;}introw0;intcolmatrix[0].length-1;// 从右上角开始while(rowmatrix.lengthcol0){intcurmatrix[row][col];if(curtarget){returntrue;}elseif(curtarget){col--;// 排除当前列}else{row;// 排除当前行}}returnfalse;}}执行示例输入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}};target5;从右上角 15 开始· 15 5 → 左移· 11 5 → 左移· 7 5 → 左移· 4 5 → 下移· 5 5 → 返回 true复杂度分析指标 复杂度时间复杂度 O(m n)空间复杂度 O(1)关键点起点选择右上角或左下角都可以因为这两个位置具有“一个方向变大、另一个方向变小”的特性便于排除。每次排除一行或一列最多移动 m n 次。边界检查空矩阵直接返回 false。对比其他方法逐行二分查找的时间复杂度为 O(m log n)而本方法更优。