【Leetcode 热题 100】74. 搜索二维矩阵

问题背景

给你一个满足下述两条属性的 $m\times n$ 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。
  给你一个整数 $target$，如果 $target$ 在矩阵中，返回 $true$；否则，返回 $false$。

数据约束

• $m=matrix.length$
• $n=matrix[i].length$
• $1\le m,n\le 100$
• $-10^4\le matrix[i][j],target\le 10^4$

解题过程

题目保证整个矩阵中的元素从上到下从左到右依次递增，也就是可以展开成一个递增的一维数组，可以用下标映射的方式，在这个虚拟的一维矩阵中进行二分搜索，时间复杂度为 $O(log(mn))$。

还可以用排除法，参考 搜索二维矩阵 II。从矩阵的右上角开始，每次比较能够去掉一行或一列，相当于查找抽象的二叉搜索树，时间复杂度大致在 $O(m+n)$ 这个量级。
具体实现

整体二分

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n;
        while(left < right) {
            int mid = left + ((right - left) >>> 1);
            int cur = matrix[mid / n][mid % n];
            if(cur == target) {
                return true;
            }
            if(cur < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return false;
    }
}

查找抽象二叉搜索树

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0) {
            int cur = matrix[i][j];
            if(cur == target) {
                return true;
            }
            if(cur < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}