阶梯查找算法,力扣题240. 搜索二维矩阵 II
程序员文章站
2022-07-14 15:18:05
...
阶梯查找法
来源:力扣(LeetCode)240. 搜索二维矩阵 II
链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii
编写一个高效的算法来搜索
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.有序数组
2.确定下一步方向确定的起始点
阶梯,就是在有序的数组有着固定的方向,只能向下向左这种意思,而问题来了,从左上角开始,如果是小于的话,会导致向下和向右都可以,所以要找到一个比较时,单方向可以的点,比如右上。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
//如果数组为空直接返回false
if(matrix.length==0){
return false;
}
//注意这是右上角,x是横向y是列数
int x=matrix[0].length-1;
int y=0;
//x是每列多少元素,所以是matrix[0].length-1
//y是有多少列,对于整个数组的长度
//注意下,向前推进到头是循环条件
while(x>=0&&y<matrix.length){
//如果当前小于目标,向下走
if(matrix[y][x]<target){
y++;
//如果当前大于目标,向左走
}else if(matrix[y][x]>target){
x--;
}else{
return true;
}
}
return false;
}
}