Medium

题目描述

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

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

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

你必须设计一个时间复杂度为 O(log(m * n)) 的解决方案。

示例 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

解题思路

这道题考查的是在有序二维矩阵中进行二分查找。由于矩阵具有特殊的排列性质（每行递增且每行首元素大于上一行末元素），整个矩阵可以看作一个按行展开的有序数组。

解法一：一次二分查找（推荐） 将二维矩阵映射为一维数组进行二分查找。对于位置 mid，可以通过 mid / n 和 mid % n 计算出对应的行列坐标。这样只需要一次二分查找，时间复杂度为 O(log(m*n))。

解法二：两次二分查找 先用二分查找确定目标值可能在哪一行，再在该行中用二分查找寻找目标值。虽然也能达到要求的时间复杂度，但需要两次二分操作。

解法三：从右上角开始搜索 从矩阵的右上角开始，根据当前值与目标值的比较结果决定向左移动还是向下移动。虽然思路简单，但时间复杂度为 O(m+n)，不满足题目要求。

推荐使用解法一，代码简洁且效率最高。

代码实现

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / n][mid % n];
            
            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
};

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            mid_value = matrix[mid // n][mid % n]
            
            if mid_value == target:
                return True
            elif mid_value < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return False

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length, n = matrix[0].Length;
        int left = 0, right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / n][mid % n];
            
            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}

var searchMatrix = function(matrix, target) {
    let m = matrix.length;
    let n = matrix[0].length;
    let left = 0;
    let right = m * n - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let row = Math.floor(mid / n);
        let col = mid % n;
        let midVal = matrix[row][col];
        
        if (midVal === target) {
            return true;
        } else if (midVal < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log(m×n))对 m×n 个元素进行二分查找
空间复杂度O(1)只使用了常数个额外变量

相关题目