十六 240. 搜索二维矩阵 II

240. 搜索二维矩阵 IIhttps://leetcode.cn/problems/search-a-2d-matrix-ii/编写一个高效的算法来搜索mxn矩阵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示例 2输入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 20输出false提示m matrix.lengthn matrix[i].length1 n, m 300-109 matrix[i][j] 109每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-109 target 109必须选一个一边是变大一边是变小的角落右上角或左下角都可以/** * 从右上角开始搜索 * 时间复杂度O(m n)最多走 mn 步 * 空间复杂度O(1) */ class Solution { public boolean searchMatrix(int[][] matrix, int target) { // 处理空矩阵的边界情况 if(matrix null || matrix.length 0 || matrix[0].length 0){ return false; } int m matrix.length;// 行数 int n matrix[0].length;//列数 int row 0;// 当前行从第0行开始 int col n - 1;// 当前列从最后一列开始 // 当还在矩阵范围内时继续搜索 // 行向下增加列向左减少 while(row m col 0){ if(matrix[row][col] target){ // 找到了 return true; }else if(matrix[row][col] target){ // 当前值太大往左移列减1 // 原因当前列的所有元素都 current target所以整列都可以排除 col--; }else{ // 当前值太小往下移行加1 // 原因当前行的所有元素都 current target所以整行都可以排除 row; } } // 走出边界了说明没找到 return false; } }