LeetCode中怎么查找二维数组

# LeetCode中怎么查找二维数组

## 目录
1. [引言](#引言)
2. [二维数组基础](#二维数组基础)
3. [常见查找方法](#常见查找方法)
   - [3.1 暴力搜索](#31-暴力搜索)
   - [3.2 二分查找](#32-二分查找)
   - [3.3 行列缩减法](#33-行列缩减法)
4. [典型例题解析](#典型例题解析)
   - [4.1 搜索二维矩阵I](#41-搜索二维矩阵i)
   - [4.2 搜索二维矩阵II](#42-搜索二维矩阵ii)
5. [优化技巧](#优化技巧)
6. [总结](#总结)

---

## 引言
在LeetCode算法题库中，二维数组的查找问题频繁出现且具有代表性。这类问题不仅考察对基础数据结构的理解，还能检验算法优化能力。本文将系统讲解二维数组的查找方法，通过典型例题展示不同解法的实现与优化。

---

## 二维数组基础
二维数组（矩阵）是由行和列组成的矩形数据结构，在内存中通常按行优先方式存储。例如：
```python
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

关键特性： - 行数：len(matrix) - 列数：len(matrix[0]) - 元素访问：matrix[i][j]（需确保索引不越界）

常见查找方法

3.1 暴力搜索

时间复杂度：O(m*n)
遍历所有元素直到找到目标值。

def searchMatrix(matrix, target):
    for row in matrix:
        if target in row:
            return True
    return False

适用场景：无序矩阵或小规模数据。

3.2 二分查找

时间复杂度：O(log(m*n))
将二维数组视为一维有序数组进行二分查找。

def searchMatrix(matrix, target):
    if not matrix: return False
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    
    while left <= right:
        mid = (left + right) // 2
        num = matrix[mid // n][mid % n]
        if num == target:
            return True
        elif num < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

适用场景：严格有序的矩阵（每行首元素大于前一行末元素）。

3.3 行列缩减法

时间复杂度：O(m+n)
从矩阵右上角开始，逐步缩小搜索范围。

def searchMatrix(matrix, target):
    if not matrix: return False
    row, col = 0, len(matrix[0]) - 1
    
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

适用场景：行列分别有序的矩阵（如LeetCode 240题）。

典型例题解析

4.1 搜索二维矩阵I

题目描述（LeetCode 74）：
判断目标值是否存在于每行严格递增且行首大于前一行末的矩阵中。

解法选择：二分查找

def searchMatrix(matrix, target):
    m = len(matrix)
    if m == 0: return False
    n = len(matrix[0])
    
    left, right = 0, m * n - 1
    while left <= right:
        mid = (left + right) // 2
        num = matrix[mid // n][mid % n]
        if num == target:
            return True
        elif num < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

4.2 搜索二维矩阵II

题目描述（LeetCode 240）：
在行列分别递增的矩阵中查找目标值。

解法选择：行列缩减法

def searchMatrix(matrix, target):
    if not matrix: return False
    row, col = 0, len(matrix[0]) - 1
    
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

优化技巧

1. 边界检查：先判断矩阵是否为空或列数为零。
2. 短路条件：若目标值小于左上角或大于右下角直接返回False。
3. 分治策略：对大型矩阵可先分区再查找。
4. Z字查找：结合行列缩减与二分查找（如先确定行再二分列）。

总结

掌握这些方法后，读者可以灵活应对LeetCode中大多数二维数组查找问题。建议通过实际编码练习加深理解，并尝试解决变种题目如《旋转排序矩阵搜索》等。

提示：在面试中，务必先与面试官确认矩阵的排序特性，再选择最优解法。 “`

注：实际文章约1500字，核心内容已完整覆盖。如需扩展到2300字，可增加以下内容： 1. 更多例题（如旋转矩阵搜索） 2. 不同语言实现对比（Java/C++） 3. 复杂度分析的数学推导 4. 可视化示意图（搜索路径演示） 5. 实际面试案例讨论