LC 240. 搜索二维矩阵 II

题目描述

这是 LeetCode 上的 240. 搜索二维矩阵 II ，难度为 中等。

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。

该矩阵具有以下特性：

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

示例 1：

输入：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

示例 2：

输入：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 = 20

输出：false

提示：

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

---

前言

这道题和之前的（题解）74. 搜索二维矩阵 类似，建议你将两题放到一起去做。

---

二分

与 （题解）74. 搜索二维矩阵 不同，本题没有确保「每行的第一个整数大于前一行的最后一个整数」，因此我们无法采取「两次二分」的做法。

只能退而求之，遍历行/列，然后再对列/行进行二分。

代码：

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 l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (matrix[i][mid] <= target) l = mid;
                else r = mid - 1;
            }
            if (matrix[i][r] == target) return true;
        }
        return false;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < n; i++) {
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (matrix[mid][i] <= target) l = mid;
                else r = mid - 1;
            }
            if (matrix[r][i] == target) return true;
        }
        return false;
    }
}

• 时间复杂度：$O(m\log{n})$ 或 $O(n\log{m})$
• 空间复杂度：$O(1)$

---

抽象 BST

该做法则与 （题解）74. 搜索二维矩阵 的「解法二」完全一致。

我们可以将二维矩阵抽象成「以右上角为根的 BST」：

那么我们可以从根（右上角）开始搜索，如果当前的节点不等于目标值，可以按照树的搜索顺序进行：

1. 当前节点「大于」目标值，搜索当前节点的「左子树」，也就是当前矩阵位置的「左方格子」，即 $c$—
2. 当前节点「小于」目标值，搜索当前节点的「右子树」，也就是当前矩阵位置的「下方格子」，即 $r$++

代码：

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

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

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.240 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。