LeetCode 74. 搜索二维矩阵

◎

本节目标

将满足行间有序关系的矩阵映射为一维有序数组后进行二分查找。

这道题把二分查找解题框架中的一维有序性延伸到二维坐标：按行展开后，元素仍然整体递增。

查看原题

题意与约束

每行从左到右递增，且下一行首元素大于上一行末元素。判断 target 是否出现在矩阵中。

朴素思路与瓶颈

逐格检查需要 O(rows * columns)；先定位可能的行再在行内查找会引入两段边界处理。题目的行间条件说明按行展开后整体仍然递增，因此可把所有位置视作一个虚拟一维数组，只做一次二分。

虚拟一维下标

若列数为 columns，一维下标 index 与坐标互相转换：

row = index / columns
column = index % columns
index = row * columns + column

这是一一对应的映射：每个矩阵位置恰好映射到一个 [0, rows * columns - 1] 下标，反过来也能还原原坐标。因此可以在虚拟数组中二分，按映射读取中点元素；比较后排除规则与普通有序数组完全相同。

代码实现

代码先防御空矩阵和空首行，再用足够宽的下标范围完成二分。

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }

        const int columns = static_cast<int>(matrix[0].size());
        long long left = 0;
        long long right = static_cast<long long>(matrix.size()) * columns - 1;
        while (left <= right) {
            const long long mid = left + (right - left) / 2;
            const int row = static_cast<int>(mid / columns);
            const int column = static_cast<int>(mid % columns);
            if (matrix[row][column] == target) {
                return true;
            }
            if (matrix[row][column] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

Python

Python 3

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False

        columns = len(matrix[0])
        left = 0
        right = len(matrix) * columns - 1
        while left <= right:
            mid = left + (right - left) // 2
            row = mid // columns
            column = mid % columns
            if matrix[row][column] == target:
                return True
            if matrix[row][column] < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

复杂度分析

• 时间复杂度：O(log(rows * columns))。
• 空间复杂度：O(1)。

易错点

• 只逐行二分会增加实现分支，也没有直接利用整体有序。
• 一维下标除以列数得到行，取模得到列，不能交换。
• [] 和 [[]] 都没有可访问元素，必须先返回 false。

模式迁移

遇到网格、分块数组或分页数据时，可先判断是否存在保序的一维映射；若存在，二维外观不妨碍二分。