[Leetcode 240] 搜索二维矩阵 II

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
写一个高效的算法来搜索 m x n 的 矩阵 matrix 中的一个目标值 target 。
该矩阵具有以下特性:
  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
 
示例 1:
notion image
 
示例 2:
notion image

解法一:“Z 字形”扫描(推荐)

矩阵按行、按列都递增。要是有个位置,能一眼判断“往上会变小,往右会变大”,那每次就能排除一整行或一整列
右上角左下角作为起点(这两个点的“局部单调方向”刚好一小一大):
  • 以右上角为例 x = 0, y = n-1
    • matrix[x][y] > target,往左走(整列右侧都更大,直接排除一列);
      < target,往下走(整行上侧都更小,直接排除一行);
      若相等就返回。
  • 这样每步至少扔掉一行或一列,最多走 m+n 步。
复杂度
  • 时间 O(m+n)
  • 空间 O(1)

解法二:二分搜索+ 轻量剪枝

既然每行有序,直觉上“在可能的行上做二分”就行;
而且还能用端点和 target 比一下,不在范围的行直接跳过
  • 先扫每一行 row,只要满足 row[0] <= target <= row[-1] 才二分。
  • 行内用标准二分找 target
也可以按列来做。 想拿到具体坐标位置,也可以。
复杂度
  • 时间:最坏 O(m log n)(m 行,每行一次二分),
  • 空间:O(1)

解法三:分治

把矩阵看成“有序的 2D 空间”。
拿中点切成四块,用中点与目标的关系去排除不可能的象限,在剩下的两块里递归
具体步骤:
  • 取子矩形左上 (r1,c1)、右下 (r2,c2),中点 (rm, cm)
  • matrix[rm][cm] == target 直接命中;
  • < target,可以排除左上上左区域,仅在右上左下递归;
  • > target,反之亦然。
  • 递归到越界/空区间就停。
复杂度
  • 时间:均摊视数据分布而定;上界可到接近 O(m log n) / O(n log m)
  • 空间: 递归栈深度 O(log(m+n))(均衡时)。
Buy Me a Coffee
上一篇
[Leetcode 239] 滑动窗口最大值
下一篇
Demystifying Agentic Search Engines