74. 搜索二维矩阵

力扣题目链接 (opens new window)

题目描述

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

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。

示例 1：

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

示例 2：

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

思路

最直接的做法是遍历整个矩阵，时间复杂度为 O(m × n)。

但这道题给出的两个有序条件很强：

• 每一行内部有序。
• 下一行的第一个元素，比上一行的最后一个元素还大。

把每一行首尾相接之后，会发生什么？

1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60

整个矩阵其实就是一个长度为 m × n 的有序数组。

那么就应该想到二分查找了。

不过我们没有必要真的创建一个新数组，那样会多使用 O(m × n) 的空间。只需要把一维下标 mid 映射回矩阵坐标即可。

假设矩阵有 n 列：

row = mid / n
col = mid % n

为什么是这两个公式？

• 每经过 n 个元素，就进入下一行，所以 mid / n 得到行号。
• mid 除以 n 的余数，就是当前元素在这一行中的列号。

例如矩阵有 4 列，一维下标 5 对应：

row = 5 / 4 = 1
col = 5 % 4 = 1

也就是 matrix[1][1] = 11。

接下来就是标准的二分查找。这里使用左闭右闭区间 [left, right]：

• 初始 left = 0，right = m × n - 1。
• 如果 matrix[row][col] < target，说明 mid 及其左侧都不可能是答案，令 left = mid + 1。
• 如果 matrix[row][col] > target，说明 mid 及其右侧都不可能是答案，令 right = mid - 1。
• 如果相等，直接返回 true。

本题的关键不是在二维矩阵里设计一套新的搜索规则，而是利用下标映射，把它还原成最熟悉的一维二分查找。

模拟过程

以 matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]、target = 13 为例。

矩阵有 3 行、4 列，可以看成下标范围为 [0, 11] 的有序数组。

第一轮，left = 0、right = 11，所以 mid = 5。

mid = 5 映射到 matrix[1][1] = 11。因为 11 < 13，下标 0 到 5 都可以排除，令 left = 6。

第二轮，搜索区间变为 [6, 11]，mid = 8。

mid = 8 映射到 matrix[2][0] = 23。因为 23 > 13，下标 8 到 11 都可以排除，令 right = 7。

第三轮，搜索区间为 [6, 7]，mid = 6。

mid = 6 映射到 matrix[1][2] = 16。因为 16 > 13，令 right = 5。此时 left > right，搜索结束，返回 false。

想清楚以下几点，本题才算理解透彻：

• 二维矩阵整体满足有序数组的性质。
• 不需要真的把矩阵复制成一维数组。
• 一维下标 mid 对应的坐标是 mid / n 和 mid % n。
• 二分查找操作的是虚拟下标区间，比较的仍然是矩阵中的真实元素。

解题代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        int left = 0;
        int right = rows * cols - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / cols;
            int col = mid % cols;
            int value = matrix[row][col];

            if (value < target) {
                left = mid + 1;
            } else if (value > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

复杂度分析

时间复杂度：O(log(m × n))，在 m × n 个虚拟下标上进行二分查找。空间复杂度：O(1)。

其他语言

Python3

class Solution:
    def searchMatrix(self, matrix, target):
        rows, cols = len(matrix), len(matrix[0])
        left, right = 0, rows * cols - 1

        while left <= right:
            mid = left + (right - left) // 2
            row, col = mid // cols, mid % cols
            value = matrix[row][col]

            if value < target:
                left = mid + 1
            elif value > target:
                right = mid - 1
            else:
                return True
        return False

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int left = 0, right = rows * cols - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / cols;
            int col = mid % cols;
            int value = matrix[row][col];

            if (value < target) {
                left = mid + 1;
            } else if (value > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

Go

func searchMatrix(matrix [][]int, target int) bool {
    rows, cols := len(matrix), len(matrix[0])
    left, right := 0, rows*cols-1

    for left <= right {
        mid := left + (right-left)/2
        row, col := mid/cols, mid%cols
        value := matrix[row][col]

        if value < target {
            left = mid + 1
        } else if value > target {
            right = mid - 1
        } else {
            return true
        }
    }
    return false
}

JS

var searchMatrix = function(matrix, target) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let left = 0, right = rows * cols - 1;

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        const row = Math.floor(mid / cols);
        const col = mid % cols;
        const value = matrix[row][col];

        if (value < target) {
            left = mid + 1;
        } else if (value > target) {
            right = mid - 1;
        } else {
            return true;
        }
    }
    return false;
};

与代码随想录联系

本题本质上还是最基础的二分查找，只是数组换成了矩阵。

如果录友对 left、right、mid 的更新规则还不熟悉，建议先看二分查找，先把左闭右闭区间的写法练熟。

本题比普通二分多做了一件事：通过除法和取模，把一维下标映射为二维坐标。

所以遇到结构看起来更复杂的数据时，不妨先想一想：它能不能通过某种映射，转换成我们已经掌握的经典模型？找到这层关系之后，题目往往就简单了。