剑指Offer面试题3 & Leetcode74
Search a 2D Matrix 二维数组中的查找
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3, return true.
解题思路
考虑：如果数组中的数小于target，那么我们将会继续在该数右方和下方寻找target；如果数组中的数大于target,那么我们将会继续在该数左方和上方寻找target，这两种可能都会导致继续寻找的区域出现重叠。
如果我们从数组右上角开始比较，就可以排除掉一个区域，不会出现重复，例如，如果该数小于target，因为该行中次数最大，所以只会去它下方继续寻找target。
Solution
public boolean searchMatrix(
int[][] matrix,
int target) {
if(matrix ==
null || matrix.length ==
0)
return false;
int row =
0;
int column = matrix[
0].length-
1;
while(row<matrix.length && column >=
0){
if(matrix[row][column] == target)
return true;
else if(matrix[row][column] > target){
column--;
}
else{
row++;
}
}
return false;
}
