【Leetcode Top 100】240. 搜索二维矩阵 II

问题背景

编写一个高效的算法来搜索$m\times n$矩阵$matrix$中的一个目标值$target$。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

数据约束

• $m==matrix.length$
• $n==matrix[i].length$
• $1\le n,m\le 300$
• $-10^9<=matrix[i][j]<=10^9$
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• $-10^9\le target\le 10^9$

解题过程

元素有序，首先想到二分法。然而本题中没有办法利用二分先确定待查找元素所在行或所在列，所以只能退而求其次遍历行或者列，再对另一个方向上用二分查找，这样做时间复杂度是 $O(mlogn)$ 或 $O(nlogm)$。

如果从矩阵右上角出发，每次判断当前元素与目标值的大小关系，那么在没找到的情况下，每次都能排除掉一行或一列。事实上因为每次查找失败时，都能明确往哪个方向进行下一步搜索，所以这个做法相当于查找抽象的二叉搜索树，时间复杂度是 $O(m+n)$。理论上这样做在数据规模特别大的情况下会优于上一种思路，但是本题中数据量不是很大，两者区别不明显。

具体实现

按行或列二分查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        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 - left) >>> 1);
                if(matrix[i][mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if(matrix[i][left] == target) {
                return true;
            }
        }
        return false;
    }
}

抽象二叉搜索树

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