Offer.P4[二维数组中的查找]

方法一：Z字形查找

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] > target) --i;
            else if (matrix[i][j] < target) ++j;
            else return true;
        }
        return false;
    }
}
  • 时间复杂度：$O(m + n)$
  • 空间复杂度：$O(1)$

方法二：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; ++i) {
            int left = 0, right = n - 1;
            while (left < right) {
                int mid = left + right >> 1;
                if (matrix[i][mid] >= target) right = mid;
                else left = mid + 1;
            }
            if (matrix[i][left] == target) return true;
        }
        return false;
    }
}
  • 时间复杂度：$O(mlogn)$
  • 空间复杂度：$O(1)$