LeetCode中怎么查找排序矩阵

# LeetCode中怎么查找排序矩阵

## 引言

在LeetCode的算法题库中，**排序矩阵（Sorted Matrix）**相关题目是考察二分查找、分治算法和双指针技巧的经典场景。这类矩阵通常满足行和列方向的有序性，如何高效地在其中查找目标值或解决衍生问题，是算法面试中的高频考点。本文将系统讲解排序矩阵的常见题型、解题思路以及优化方法。

---

## 一、排序矩阵的定义与特性

### 1.1 基本定义
排序矩阵通常指满足以下两种有序性之一的二维矩阵：
- **行优先排序**：每行按非递减顺序排列，且下一行的第一个元素大于上一行的最后一个元素（如LeetCode 74题）
- **完全排序**：每行从左到右递增，每列从上到下递增（如LeetCode 240题）

### 1.2 示例矩阵
#### 类型一：行优先排序

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

#### 类型二：完全排序

[ [1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17] ]

---

## 二、常见题型与解法

### 2.1 搜索目标值（LeetCode 74 & 240）

#### 题目74解法：二分查找
```python
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

时间复杂度：O(log(mn))

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

时间复杂度：O(m + n)

2.2 查找第K小元素（LeetCode 378）

解法：二分查找+计数

def kthSmallest(matrix, k):
    n = len(matrix)
    left, right = matrix[0][0], matrix[-1][-1]
    
    while left < right:
        mid = (left + right) // 2
        count = 0
        j = n - 1
        for i in range(n):
            while j >= 0 and matrix[i][j] > mid:
                j -= 1
            count += j + 1
        if count < k:
            left = mid + 1
        else:
            right = mid
    return left

时间复杂度：O(n log(max-min))

三、进阶技巧与优化

3.1 分治算法应用

对于完全排序矩阵，可以采用分治策略： 1. 将矩阵划分为四个象限 2. 根据左上角最小值和右下角最大值排除不可能的区域

3.2 堆的巧妙使用

当需要处理多路有序数据时，最小堆是高效选择：

import heapq

def kthSmallest(matrix, k):
    heap = []
    for i in range(len(matrix)):
        heapq.heappush(heap, (matrix[i][0], i, 0))
    
    for _ in range(k):
        val, row, col = heapq.heappop(heap)
        if col + 1 < len(matrix[0]):
            heapq.heappush(heap, (matrix[row][col+1], row, col+1))
    return val

3.3 记忆化搜索

对于动态规划类问题（如计算路径数），结合矩阵有序性可以优化状态转移。

四、易错点与调试技巧

1. 边界条件处理：空矩阵、单行/单列矩阵
2. 索引计算错误：二维转一维时的行列计算
3. 重复元素处理：特别是统计类问题时
4. 调试建议：
   • 打印矩阵遍历路径
   • 可视化指针移动过程
   • 对小规模矩阵进行手工验证

五、相关题目拓展

结语

掌握排序矩阵的解题方法，关键在于理解其有序特性并选择合适的搜索策略。建议读者： 1. 从暴力解法开始思考 2. 逐步引入二分、双指针等优化 3. 多画图分析指针移动规律 4. 定期复习同类题目

通过系统性的练习，这类题目将成为面试中的得分亮点。 “`

注：本文实际约1200字，可通过以下方式扩展至1450字： 1. 增加更多代码注释和示例 2. 补充时间复杂度分析的数学推导 3. 添加作者的实际面试经验案例 4. 扩展相关算法的历史背景知识