240. 搜索二维矩阵 II

力扣题目链接 (opens new window)

题目描述

编写一个高效的算法来搜索 m × 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

思路

很明显暴力的解法是遍历整个矩阵，时间复杂度O(m × n)。

但题目说了矩阵是有序的——每行从左到右递增，每列从上到下递增。那么就应该利用这个有序性了。

看到有序，很多录友第一反应是二分查找。确实可以对每一行做二分，时间复杂度O(m × log n)，已经比暴力好了。

但本题有更巧妙的解法：从右上角（或左下角)开始搜索。

为什么从右上角开始？

因为右上角的元素有个特点：

• 它是当前行的最大值
• 它是当前列的最小值

这意味着：如果target比它小，那target一定在它左边；如果target比它大，那target一定在它下面。

这样每次比较，都能排除一行或一列，时间复杂度降到O(m + n)。

具体逻辑：

1. 从右上角 (0, n-1) 开始
2. 如果当前元素等于target，返回true
3. 如果当前元素大于target，左移（排除当前列）
4. 如果当前元素小于target，下移（排除当前行）
5. 如果越界还没找到，返回false

从左下角开始也是一样的思路，因为左下角也具有"是当前行最小值，是当前列最大值"的性质。

模拟过程

以示例 1 为例，target = 5：

初始化：从右上角开始

步骤 1：15 > 5，左移

经过几步左移和下移后：

找到目标：5 == 5

初始矩阵：
 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

步骤 1：current = 15 > 5，左移 步骤 2：current = 11 > 5，左移 步骤 3：current = 7 > 5，左移 步骤 4：current = 4 < 5，下移 步骤 5：current = 5 == 5，找到！

解题代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        // 从右上角开始
        int row = 0;
        int col = n - 1;
        
        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--; // 当前元素大于target，左移排除当前列
            } else {
                row++; // 当前元素小于target，下移排除当前行
            }
        }
        
        return false;
    }
};

复杂度分析

• 时间复杂度：O(m + n)，每次移动排除一行或一列，最多移动 m + n 次
• 空间复杂度：O(1)，只用了两个指针变量

其他语言

Python3

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        
        # 从右上角开始
        row, col = 0, n - 1
        
        while row < m and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1  # 当前元素大于target，左移
            else:
                row += 1  # 当前元素小于target，下移
        
        return False

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // 从右上角开始
        int row = 0;
        int col = n - 1;
        
        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--; // 当前元素大于target，左移
            } else {
                row++; // 当前元素小于target，下移
            }
        }
        
        return false;
    }
}

Go

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    
    // 从右上角开始
    row, col := 0, n-1
    
    for row < m && col >= 0 {
        if matrix[row][col] == target {
            return true
        } else if matrix[row][col] > target {
            col-- // 当前元素大于target，左移
        } else {
            row++ // 当前元素小于target，下移
        }
    }
    
    return false
}

JavaScript

var searchMatrix = function(matrix, target) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    // 从右上角开始
    let row = 0;
    let col = n - 1;
    
    while (row < m && col >= 0) {
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--; // 当前元素大于target，左移
        } else {
            row++; // 当前元素小于target，下移
        }
    }
    
    return false;
};

与代码随想录联系

这道题和代码随想录里的 74. 搜索二维矩阵 看起来类似，但有区别：

• 74题的矩阵更严格：每行第一个元素大于前一行最后一个元素，所以可以看成一维有序数组，用二分查找
• 本题只保证行内有序、列内有序，但行与行之间有交叉，所以要用右上角/左下角的双指针法

在代码随想录的矩阵专题中，会系统讲解矩阵的各种遍历和搜索技巧。想进一步学习可以看 代码随想录数组章节。