每日一题，提升自己。今天分享一道关于二维数组中查询的题目，且听我细细道来。

数组 - 二维数组中查询

1. 题目描述

        在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例：

现有矩阵 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=6，返回false

提示：

限制：

0 <= n <= 1000

0 <= m <= 1000

2. 解题思路

        本题可以通过遍历数组来进行查找，不过显然这是最笨的方法，时间复杂度很高，但是我们可以换一种方法去遍历。首先结合题目观察矩阵发现，左下角的数字，上方的数组都小于它，右方的数字都大于它。该规律可应用于矩阵中的每一个数，所以可以根据该规律去进行判断。

复杂度：

• 时间复杂度：O(m+n)。

3. 算法流程

1. 设当前数字为最左下角的数字cur，目标数为target。
2. 初始化当前数字角标，x=matrix.length-1,y=0。
3. 如果target > cur：则向右查找，即y++。
4. 如果target < cur：则向上查找，即x–。
5. 如果target == cul：则返回true。
6. 否则直到数组边界，返回false。

4. 代码实现

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static boolean findNumberIn2DArra(int[][] matrix, int target){
    if(matrix.length == 0)
        return false;
    
    int x = matrix.length-1,y = 0;
    while (x >= 0 && y < matrix[0].length){
        if (target > matrix[x][y]){
            y++;
        }else if (target < matrix[x][y]){
            x--;
        }else {
            return true;
        }
    }
    return false;
}