欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

阶梯查找算法,力扣题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;

    }

}