leetcode题 搜索二维矩阵

搜索二维矩阵 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。

首先分析题目,给出的是一个二维数组,我们需要寻找的是他给出的target值((ó﹏ò。)开始没看懂题目,想了半天...)。
接下来,我们分析他的特性。每行的元素从左到右是升序,每列的元素从上到下也是升序。ps:当然你也可以使用暴力破解,就不需要看这个特性了,不过时间复杂度为n2。如果他什么特性都没有,到是可以使用暴力,不过他既然给出了条件;那肯定要用上的。那我们继续观察这个二维数组。我们知道在线性表中有一个算法是二分查找,并且它的时间复杂度为logn。最开始我也想过用二分查找,但是最后还是放弃了,主要是不好写。
那么我们还有什么方法呢?首先这个数组行列是有序的,那么我们可以找一个地方开始遍历。首先从角落入手,我们看看matrix0好用不,如果我们选择这个点,因为它是最小的。那么当target大于它时,我们就不好选择走哪里了。同理,它的对角点也是。那么我们从左下(matrix4)或右上(matrix0)来走。选择这两个点有个好处,就是我们知道该怎么走,因为它只是行中最大或列中最大的数,然后我们可以根据它和target值得对比来决定往哪里走。

class Solution {
    
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0)
            return false;
        int row = 0;  //行
        int col = matrix[0].length-1;  //列
        System.out.println(row + " " + col);
        while(row <= matrix.length-1 && col >= 0){
            if(matrix[row][col] == target){
                System.out.println(matrix[row][col]);
                return true;
            }else if(matrix[row][col] > target){
                System.out.println("col:"+matrix[row][col]);
                col --;
            }else if(matrix[row][col] < target){
                System.out.println("row:"+matrix[row][col]);
                row ++;
            }
        }
        return false;
    }
}
Last modification:September 20th, 2019 at 07:26 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment