深入解析二维矩阵搜索：LeetCode 74与240题的两种高效解法对比

文章目录

• • @[toc]
  • • • **引言**
    • **一、问题背景与排序规则对比**
    • • **1. LeetCode 74. 搜索二维矩阵**
      • **2. LeetCode 240. 搜索二维矩阵 II**
    • **二、核心解法对比**
    • • **方法1：二分查找法（适用于LeetCode 74）**
      • **方法2：线性缩小搜索范围法（适用于LeetCode 240）**
    • **三、关键差异与适用场景**
    • **四、为什么解法不能互换？**
    • • **1. 二分查找法在LeetCode 240中的失效示例**
      • **2. 线性缩小法在LeetCode 74中的效率问题**
    • **五、边界情况处理**
    • • **1. 空矩阵或空行**
      • **2. 单元素矩阵**
      • **3. 单行或单列矩阵**
    • **六、总结与建议**

引言

在算法面试中，二维矩阵搜索问题频繁出现，其中 LeetCode 74. 搜索二维矩阵 和 LeetCode 240. 搜索二维矩阵 II 是两道经典的题目。尽管题目名称相似，但它们的矩阵排序规则和解题思路存在显著差异。本文将从问题本质出发，对比两种解法的核心思想、适用场景及实现细节，帮助读者深入理解并灵活应对类似问题。

---

一、问题背景与排序规则对比

1. LeetCode 74. 搜索二维矩阵

• 题目描述
  在一个 m x n 的二维矩阵中，每一行元素严格递增，且下一行的第一个元素严格大于上一行的最后一个元素。要求判断目标值 target 是否存在于矩阵中。
• 排序特性
  整个矩阵可以视为一个全局有序的一维数组，例如：

  [[1, 3, 5, 7],[10,11,16,20],[23,30,34,60]]
  

  展开后为一维数组：[1,3,5,7,10,11,16,20,23,30,34,60]。

2. LeetCode 240. 搜索二维矩阵 II

• 题目描述
  在一个 m x n 的二维矩阵中，每一行元素从左到右递增，每一列元素从上到下递增，但行与行之间没有严格的大小关系。要求判断目标值是否存在。
• 排序特性
  矩阵仅局部有序，无法直接展开为全局有序的一维数组，例如：

  [[1, 4, 7],[2, 5, 8],[3, 6, 9]]
  

---

二、核心解法对比

方法1：二分查找法（适用于LeetCode 74）

• 核心思想
  将二维矩阵映射为一维数组，利用二分查找直接定位目标值。

• 时间复杂度
  (O(\log(m \times n)))，其中 (m) 为行数，(n) 为列数。

• 实现步骤

  1. 将二维索引映射为一维：index = row * n + col。
  2. 通过一维索引的二分查找确定目标值的位置。
  3. 转换回二维索引进行值比较。

• Java代码实现

  class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;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 row = mid / n;  // 计算行坐标int col = mid % n;  // 计算列坐标if (matrix[row][col] == target) {return true;} else if (matrix[row][col] < target) {left = mid + 1;} else {right = mid - 1;}}return false;}
  }
  

方法2：线性缩小搜索范围法（适用于LeetCode 240）

• 核心思想
  从矩阵的右上角（或左下角）出发，通过逐步排除行或列缩小搜索范围。

• 时间复杂度
  (O(m + n))，其中 (m) 为行数，(n) 为列数。

• 实现步骤

  1. 初始化位置为右上角 (0, n-1)。
  2. 若当前值等于目标值，返回 true。
  3. 若当前值大于目标值，向左移动一列；否则向下移动一行。
  4. 重复直至越界。

• Java代码实现

  class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;int m = matrix.length, n = matrix[0].length;int row = 0, col = n - 1;  // 从右上角开始搜索while (row < m && col >= 0) {int current = matrix[row][col];if (current == target) {return true;} else if (current > target) {col--;  // 排除当前列} else {row++;  // 排除当前行}}return false;}
  }
  

---

三、关键差异与适用场景

对比维度	二分查找法（LeetCode 74）	线性缩小法（LeetCode 240）
时间复杂度	(O(\log(mn)))（对数级，高效）	(O(m + n))（线性级，适用于中等规模矩阵）
空间复杂度	(O(1))（原地操作）	(O(1))（原地操作）
排序规则依赖	必须全局有序	仅需局部行列有序
适用题目	仅LeetCode 74	仅LeetCode 240（但LeetCode 74也可用）
优势场景	大规模全局有序矩阵	局部有序或中等规模矩阵

---

四、为什么解法不能互换？

1. 二分查找法在LeetCode 240中的失效示例

• 矩阵示例

  [[1, 3, 5],[2, 4, 6],[7, 8, 9]
  ]
  

• 搜索目标：2
  • 一维展开为 [1,3,5,2,4,6,7,8,9]，二分查找时中间值可能跳过实际存在的元素，导致错误结果。

2. 线性缩小法在LeetCode 74中的效率问题

• 矩阵示例

  [[1, 3, 5, 7],[10,11,16,20],[23,30,34,60]
  ]
  

• 搜索目标：60
  • 从右上角开始需遍历 7 → 20 → 60，时间复杂度为 (O(n))，而二分查找仅需 (O(\log 12) \approx 4) 次比较。

---

五、边界情况处理

1. 空矩阵或空行

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

2. 单元素矩阵

• 矩阵为 [[5]]，目标值为 5 时直接返回 true。

3. 单行或单列矩阵

• 单行矩阵 [[1,3,5]] 或单列矩阵 [[2],[4],[7]]，两种方法均能正确处理。

---

六、总结与建议

1. LeetCode 74（全局有序）

   • 优先选择二分查找法，时间复杂度更低，适合大规模数据。
   • 若使用线性缩小法，虽然可行，但效率略低。

2. LeetCode 240（局部有序）

   • 必须使用线性缩小法，二分查找法因全局无序可能失效。
   • 从右上角或左下角出发均可，逻辑对称。

3. 实际应用场景

   • 数据库索引查询（全局有序场景）。
   • 图像处理中的局部特征搜索（局部有序场景）。

---

通过深入理解矩阵的排序规则与算法特性，读者可以灵活选择最优解法，轻松应对二维矩阵搜索问题。无论是面试还是实际工程应用，清晰的思路和高效的代码实现都是解决问题的关键。