LeetCode 240 搜索二维矩阵 II

题目：

https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=selected-coding-interview

问题描述

LeetCode 240题要求在一个二维矩阵中搜索目标值。该矩阵具有以下特性：

• 每行元素从左到右升序排列。
• 每列元素从上到下升序排列。

例如：

matrix = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
target = 5
输出：true（矩阵中存在目标值5）

解题思路：Z字形搜索法

该矩阵的特殊性质（每行每列均有序）允许我们从矩阵的右上角（或左下角）开始搜索，将时间复杂度优化到 O(m+n)（m和n分别为矩阵的行数和列数）。具体步骤如下：

1. 选择起始点：从矩阵的右上角（即第一行的最后一列，坐标为(0, n-1)）开始。
2. 比较目标值：
   • 若当前元素等于目标值，返回true。
   • 若当前元素大于目标值，向左移动一列（因为当前列下方的所有元素都更大，不可能包含目标值）。
   • 若当前元素小于目标值，向下移动一行（因为当前行左侧的所有元素都更小，不可能包含目标值）。
3. 重复步骤2：直到越界（行索引超出m或列索引小于0），此时返回false。

代码实现

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        
        int m = matrix.size();    // 行数
        int n = matrix[0].size(); // 列数
        int row = 0, col = n - 1; // 从右上角开始
        
        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true; // 找到目标值
            } else if (matrix[row][col] > target) {
                col--; // 当前元素大于目标值，向左移动
            } else {
                row++; // 当前元素小于目标值，向下移动
            }
        }
        
        return false; // 越界，未找到目标值
    }
};

代码解释

1. 初始化：

   • row = 0：从第一行开始。
   • col = n - 1：从最后一列开始（右上角）。

2. 循环搜索：

   • 相等条件：若当前元素等于目标值，直接返回true。
   • 大于条件：若当前元素大于目标值，说明目标值只能在当前列的左侧，因此col--。
   • 小于条件：若当前元素小于目标值，说明目标值只能在当前行的下方，因此row++。

3. 终止条件：

   • 若row超出矩阵行数或col小于0，说明搜索区域已越界，返回false。

复杂度分析

• 时间复杂度：O(m+n)
  每次迭代要么行增加1，要么列减少1，最多需要遍历m行+n列。

• 空间复杂度：O(1)
  只需要常数级的额外空间。

为什么选择右上角？

右上角的元素是该行的最大值、该列的最小值。这一特性使得：

• 若当前元素大于目标值，可以排除当前列的所有元素（下方元素更大）。
• 若当前元素小于目标值，可以排除当前行的所有元素（左侧元素更小）。

同理，从左下角（最后一行的第一列）开始搜索也可以达到相同效果，但从左上角或右下角开始无法有效缩小搜索区域。

示例演示

假设搜索target = 5：

[1,   4,  7, 11, 15]  ← 从右上角开始（值=15，大于5，向左移动）
[2,   5,  8, 12, 19]
[3,   6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

[1,   4,  7, 11, 15]
[2,   5,  8, 12, 19]  ← 移动到11（仍大于5，继续向左）
[3,   6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

[1,   4,  7, 11, 15]
[2,   5,  8, 12, 19]  ← 移动到7（仍大于5，继续向左）
[3,   6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

[1,   4,  7, 11, 15]
[2,   5,  8, 12, 19]  ← 移动到4（小于5，向下移动）
[3,   6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

[1,   4,  7, 11, 15]
[2,   5,  8, 12, 19]  ← 移动到5（等于目标值，返回true）
[3,   6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

这种方法通过逐步缩小搜索区域，高效地找到目标值或确定其不存在。