二维数组中的查找

题目描述

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

示例:
现有矩阵 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。

限制：
0 <= m <= 1000
0 <= n <= 1000

题目链接

Leetcode

题目解答

解法一

暴力查找，即遍历数组中的每一个元素，如果元素的值与target相等，则返回true，否则返回false。

时间复杂度:$O(mn)$ 空间复杂度:$O(1)$

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：44 MB, 在所有 Java 提交中击败了85.50%的用户

解法二

线性查找，在解法一中，暴力查找明显没有充分利用数据的特征，数组元素本身在一定程度上是有序的，我们利用这种有序性可以有效降低查找的次数。不难发现以数组右上角的值作为起始值与target进行比较，如果值比target大，继续往下查找，如果值比target小，继续往左查找，如果超过了数组的边界，或者查找的位置到达了左下角也没能找到target则返回false，如果找到了则返回true。查找过程中，往左最多查找n次，往下最多查找m次，总的查找次数不超过m + n次。

时间复杂度:$O(m + n)$ 空间复杂度:$O(1)$

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] < target) {
                x++;
            } else {
                y--;
            }
        }
        return false;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：43.9 MB, 在所有 Java 提交中击败了92.41%的用户