LC.P74[搜索二维矩阵]

方法一：二分

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (matrix[mid / n][mid % n] >= target) right = mid;
            else left = mid + 1;
        }
        return matrix[left / n][left % n] == target;
    }
}
  • 时间复杂度：$O(log(mn))$
  • 空间复杂度：$O(1)$

方法二：抽象BST

将矩阵向左旋转45°，即可抽象为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    
    int m, n;

    public boolean searchMatrix(int[][] matrix, int target) {
        m = matrix.length;
        n = matrix[0].length;
        int x = 0, y = n - 1;
        while (check(x, y) && matrix[x][y] != target) {
            if (matrix[x][y] > target) --y;
            else ++x;
        }
        return check(x, y) && matrix[x][y] == target;
    }

    private boolean check(int x, int y) {
        return 0 <= x && x < m && 0 <= y && y < n;
    }
}
  • 时间复杂度：$O(m + n)$
  • 空间复杂度：$O(1)$