Medium

题目描述

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

解题思路

这道题有多种解法，我们重点分析最优的右上角搜索法。

思路分析：

由于矩阵的行列都是升序的，我们可以利用这个特性进行高效搜索。关键观察是选择合适的起始位置。

方法一：右上角搜索法（推荐）

  • 从矩阵的右上角开始搜索，这个位置具有特殊性质：
    • 它是该行的最大值
    • 它是该列的最小值
  • 比较当前元素与目标值：
    • 如果当前值等于目标值，找到了
    • 如果当前值大于目标值，目标值不可能在当前列，向左移动
    • 如果当前值小于目标值，目标值不可能在当前行，向下移动

其他方法：

  • 方法二：暴力搜索，时间复杂度O(mn)
  • 方法三：对每行进行二分搜索，时间复杂度O(m log n)
  • 方法四：分治法，时间复杂度O(n log m)

右上角搜索法最优，时间复杂度仅为O(m+n)。

代码实现

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int row = 0, col = n - 1;
        
        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        
        return false;
    }
};

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
            else:
                row += 1
        
        return False

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length, n = matrix[0].Length;
        int row = 0, col = n - 1;
        
        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        
        return false;
    }
}

var searchMatrix = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let row = 0, col = n - 1;
    
    while (row < m && col >= 0) {
        if (matrix[row][col]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
右上角搜索法O(m + n)O(1)
暴力搜索O(m × n)O(1)
每行二分搜索O(m × log n)O(1)

其中 m 为矩阵的行数，n 为矩阵的列数。右上角搜索法是最优解。

相关题目