LeetCode 240. 搜索二维矩阵 II [Hot 100] —— Z字形查找

240. 搜索二维矩阵 II

中等

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

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

示例 1：

输入：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

示例 2：

输入：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 = 20
输出：false

Z字形查找算法

算法思路

从矩阵的右上角（或左下角）开始搜索：

• 如果当前值 等于 target → 找到目标，返回true
• 如果当前值 大于 target → 向左移动一列（排除当前列）
• 如果当前值 小于 target → 向下移动一行（排除当前行）

代码实现

java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        // 从右上角开始
        int row = 0;
        int 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;
    }
}

算法演示

以 matrix = [[1,4],[2,5]], target = 2 为例：

text

初始状态：从右上角(0,1)=4开始
[1, 4]
[2, 5]
 ↑
(0,1)=4

步骤1: 4 > 2 → 向左移动到(0,0)=1
[1, 4]
[2, 5]
 ↑
(0,0)=1

步骤2: 1 < 2 → 向下移动到(1,0)=2
[1, 4]
[2, 5]
     ↑
(1,0)=2 → 找到目标！

为什么Z字形查找有效？

1. 利用矩阵的有序性：

   • 每行从左到右递增
   • 每列从上到下递增

2. 搜索路径最优：

   • 从右上角开始，每次移动都能排除一行或一列
   • 搜索路径呈"Z"字形

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

   • 最坏情况下从右上角走到左下角
   • 每次循环排除一行或一列