题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例:
现有矩阵 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。 给定 target = 20,返回 false。
思路
1.根据此二维矩阵给出的性质,可以从二维数组的右上角开始搜索,若target大于当前元素,我们的检索方向就向下,若小于,我们的检索方向就向左,若检索出界,还没找到结果,直接返回false即可。。
Java代码实现
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length == 0){ return false; } int rowIndex = 0; int colIndex = matrix[0].length-1; while(rowIndex < matrix.length && colIndex >= 0){ if(matrix[rowIndex][colIndex] == target){ return true; }else if(matrix[rowIndex][colIndex] > target){ colIndex--; }else{ rowIndex++; } } return false; } }
Golang代码实现
func searchMatrix(matrix [][]int, target int) bool { if len(matrix) == 0{ return false } rowIndex,colIndex := 0, len(matrix[0])-1 for rowIndex < len(matrix) && colIndex >= 0 { if matrix[rowIndex][colIndex] == target{ return true }else if matrix[rowIndex][colIndex] > target{ colIndex-- }else { rowIndex++ } } return false }