LC 74. 搜索二维矩阵

题目描述

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

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

1
2
3

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出：true

示例 2：

1
2
3

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出：false

提示：

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

二分（一）

由于二维矩阵固定列的「从上到下」或者固定行的「从左到右」都是升序的。

因此我们可以使用两次二分来定位到目标位置：

第一次二分：从第 0 列中的「所有行」开始找，找到合适的行 row
第二次二分：从 row 中「所有列」开始找，找到合适的列 col

Java 代码：

class Solution {
    public boolean searchMatrix(int[][] mat, int t) {
        int m = mat.length, n = mat[0].length;
        // 第一次二分：定位到所在行（从上往下，找到最后一个满足 mat[x]][0] <= t 的行号）
        int l = 0, r = m - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mat[mid][0] <= t) l = mid;
            else r = mid - 1;
        }
        int row = r;
        if (mat[row][0] == t) return true;
        if (mat[row][0] > t) return false;
        // 第二次二分：从所在行中定位到列（从左到右，找到最后一个满足 mat[row][x] <= t 的列号）
        l = 0; r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mat[row][mid] <= t) l = mid;    
            else r = mid - 1;
        }
        int col = r;
        return mat[row][r] == t;
    }
}

C++ 代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& mat, int t) {
        int m = mat.size(), n = mat[0].size();
        // 第一次二分：定位到所在行
        int l = 0, r = m - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mat[mid][0] <= t) l = mid;
            else r = mid - 1;
        }
        int row = r;
        if (mat[row][0] == t) return true;
        if (mat[row][0] > t) return false;
        // 第二次二分：从所在行中定位到列
        l = 0; r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mat[row][mid] <= t) l = mid;
            else r = mid - 1;
        }
        int col = r;
        return mat[row][l] == t;
    }
};

Python 代码：

class Solution:
    def searchMatrix(self, mat, t):
        m, n = len(mat), len(mat[0])
        # 第一次二分：定位到所在行
        l, r = 0, m - 1
        while l < r:
            mid = l + r + 1 >> 1
            if mat[mid][0] <= t:
                l = mid
            else:
                r = mid - 1
        row = r
        if mat[row][0] == t:
            return True
        if mat[row][0] > t:
            return False
        # 第二次二分：从所在行中定位到列
        l, r = 0, n - 1
        while l < r:
            mid = l + r + 1 >> 1
            if mat[row][mid] <= t:
                l = mid
            else:
                r = mid - 1
        col = r
        return mat[row][l] == t

TypeScript 代码：

function searchMatrix(mat: number[][], t: number): boolean {
    const m = mat.length, n = mat[0].length;
    // 第一次二分：定位到所在行
    let l = 0, r = m - 1;
    while (l < r) {
        const mid = l + r + 1 >> 1;
        if (mat[mid][0] <= t) l = mid;    
        else r = mid - 1;
    }
    const row = r;
    if (mat[row][0] == t) return true;
    if (mat[row][0] > t) return false;
    // 第二次二分：从所在行中定位到列
    l = 0; r = n - 1;
    while (l < r) {
        const mid = l + r + 1 >> 1;
        if (mat[row][mid] <= t) l = mid;    
        else r = mid - 1;
    }
    const col = r;
    return mat[row][l] == t;
};

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

二分（二）

当然，因为将二维矩阵的行尾和行首连接，也具有单调性。

我们可以将「二维矩阵」当做「一维矩阵」来做。

Java 代码：

class Solution {
    public boolean searchMatrix(int[][] mat, int t) {
        int m = mat.length, n = mat[0].length;
        int l = 0, r = m * n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mat[mid / n][mid % n] <= t) l = mid;    
            else r = mid - 1;
        }
        return mat[r / n][r % n] == t;
    }
}

C++ 代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& mat, int t) {
        int m = mat.size(), n = mat[0].size();
        int l = 0, r = m * n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mat[mid / n][mid % n] <= t) l = mid;
            else r = mid - 1;
        }
        return mat[l / n][l % n] == t;
    }
};

Python 代码：

class Solution:
    def searchMatrix(self, mat, t):
        m, n = len(mat), len(mat[0])
        l, r = 0, m * n - 1
        while l < r:
            mid = l + r + 1 >> 1
            if mat[mid // n][mid % n] <= t:
                l = mid
            else:
                r = mid - 1
        return mat[l // n][l % n] == t

TypeScript 代码：

function searchMatrix(mat: number[][], t: number): boolean {
    const m = mat.length, n = mat[0].length;
    let l = 0, r = m * n - 1;
    while (l < r) {
        const mid = l + r + 1 >> 1;
        if (mat[Math.floor(mid / n)][mid % n] <= t) l = mid;    
        else r = mid - 1;
    }
    return mat[Math.floor(l / n)][l % n] === t;
};

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

抽象 BST

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

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

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

Java 代码：

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

C++ 代码：

class Solution {
public:
    int m, n;
    bool searchMatrix(vector<vector<int>>& mat, int t) {
        m = mat.size(); n = mat[0].size();
        int x = 0, y = n - 1;
        while (check(x, y) && mat[x][y] != t) {
            if (mat[x][y] > t) y--;
            else x++;
        }
        return check(x, y) && mat[x][y] == t;
    }
    bool check(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
};

Python 代码：

class Solution:
    def searchMatrix(self, mat, t):
        m, n = len(mat), len(mat[0])
        x, y = 0, n - 1
        while self.check(m, n, x, y) and mat[x][y] != t:
            if mat[x][y] > t:
                y -= 1
            else:
                x += 1
        return self.check(m, n, x, y) and mat[x][y] == t
    def check(self, m, n, x, y):
        return 0 <= x < m and 0 <= y < n

TypeScript 代码：

function check(m: number, n: number, x: number, y: number): boolean {
    return x >= 0 && x < m && y >= 0 && y < n;
}
function searchMatrix(mat: number[][], t: number): boolean {
    const m = mat.length, n = mat[0].length;
    let x = 0, y = n - 1;
    while (check(m, n, x, y) && mat[x][y] !== t) {
        if (mat[x][y] > t) y--;
        else x++;
    }
    return check(m, n, x, y) && mat[x][y] === t;
};

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

拓展

如果你掌握了上述解法的话，你还可以试试这题：

240. 搜索二维矩阵 II

最后

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

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

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

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

二分二叉搜索树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 90. 子集 II 上一篇

LC 190. 颠倒二进制位下一篇