240. 搜索二维矩阵 II/面试题04. 二维数组中的查找(简单)

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例:

现有矩阵 matrix 如下：

1
2
3
4
5
6
7
[
  [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。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii

思路1:

暴力法，全部遍历，遇到就找到了

思路2：

我们从矩阵的右上角开始遍历，如果该数字就等于要查找的数，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行，也就是说，如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小范围，知道找到要找的数，或者搜索到矩阵为空为止。

回看记录200604

由于向右也增，向下也增，所以右上的会比该数大，然后往下找，往左找，其实也可以从左下往右上找，思路是一样的

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //暴力法
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;
        for(int i = 0;i<matrix.length;i++){//行
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]==target)
                    return true;
            }
        }
        return false;
    }
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length==0|| matrix[0].length==0){
            return false;
        }
        int m = 0;
        int n = matrix[0].length-1;
        //从右上角开始找
        while (n>=0 && matrix.length>m){
            int res = matrix[m][n];
            //如果大于目标值
            if(res>target){
                n--;
            }else if(res<target){
                m++;
            }else if(res==target){
                return true;
            }
        }
        return false;
    }
}