当前位置：首页 > news >正文

64.搜索二维矩阵

news 2026/3/26 22:50:33

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

我的思路：

从当前层第一个元素开始

判断 target 是否在当前层 1<3<10，在当前层 j++ if(matrix[i][j] == target) return true;

else if 在下一层 continue;

else 不存在。// 上一层，逐层往下遍历，不可能在上一层。

用到了matrix[i+1][0] ，所以分类判断是否是最后一行，最后一行直接遍历。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int n = matrix.length;for(int i = 0; i < n; i++){   if(i<n-1){// 当前层if(matrix[i+1][0] > target && matrix[i][0]<= target){for(int j=0; j<matrix[0].length;j++)if(matrix[i][j] == target) return true;return false;}// 下一层else if(matrix[i+1][0] <= target) continue;else return false; // 上一层
            }     else{   // 处理最后一层for(int j=0; j<matrix[0].length;j++)if(matrix[i][j] == target) return true;}}return false;}
}

【别人的方法没找到来源】

从当前层最后一个元素开始

不在当前层

target > matrix[i][n-1]  i++;

在当前层

target < matrix[i][n-1] j--;

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;for(int i = 0, j = n-1; i < m && j >= 0; ){if(target > matrix[i][j]){i++;}else if(target < matrix[i][j]){j--;}else{return true;}}return false;}
}