【LeetCode 热题 100】240. 搜索二维矩阵 II——排除法

Problem: 240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

整体思路

这段代码旨在解决一个经典的矩阵搜索问题：搜索二维矩阵 II (Search a 2D Matrix II)。问题要求在一个特殊的 M x N 矩阵中高效地查找一个目标值 target。这个矩阵的特殊之处在于：

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

该算法采用了一种非常巧妙且高效的 “Z”字形（或称为“锯齿形”）查找法。它利用了矩阵的行列双重有序性，以线性的时间复杂度完成搜索。

1. 选择起点：

   • 算法的关键在于选择一个合适的起点。它选择了矩阵的 右上角 (0, n-1) 作为起始搜索点。
   • 为什么是右上角（或左下角）：这个位置非常特殊。对于右上角的元素 matrix[i][j]：
     • 它小于同一行右侧的所有元素（不存在）。
     • 它大于同一行左侧的所有元素。
     • 它小于同一列下方的所有元素。
     • 它大于同一列上方的所有元素（不存在）。
   • 这种特性使得每一次比较都能排除掉一整行或一整列的元素，从而实现高效的搜索。

2. 搜索路径与排除逻辑：

   • 算法使用一个 while 循环来持续搜索，只要指针 (i, j) 还在矩阵范围内（i < m && j >= 0）。
   • 在循环的每一步，将当前指针指向的元素 matrix[i][j] 与 target 进行比较：
     • Case 1: matrix[i][j] == target
       • 找到了目标值，直接返回 true。
     • Case 2: matrix[i][j] < target
       • 由于当前元素 matrix[i][j] 比 target 小，并且它已经是当前行 i 中最大的元素（因为我们从最右边开始），所以 target 不可能在当前行的任何位置。
       • 因此，我们可以安全地排除掉整个第 i 行，并将搜索范围向下移动一行。实现方式是 i++。
     • Case 3: matrix[i][j] > target
       • 由于当前元素 matrix[i][j] 比 target 大，并且它已经是当前列 j 中最小的元素（因为我们从最上边开始），所以 target 不可能在当前列的任何位置。
       • 因此，我们可以安全地排除掉整个第 j 列，并将搜索范围向左移动一列。实现方式是 j--。

3. 终止条件：

   • while 循环会一直持续，直到指针移出矩阵边界（i 越过下边界或 j 越过左边界）。
   • 如果循环结束了还没有找到 target，就说明目标值在矩阵中不存在，返回 false。

这个算法的路径就像在矩阵中画一条从右上到左下的折线，每一步都剔除一行或一列，因此效率非常高。

完整代码

class Solution {
    /**
     * 在一个行列都升序的矩阵中高效地查找一个目标值。
     * @param matrix 一个 M x N 的整数矩阵，每行从左到右升序，每列从上到下升序。
     * @param target 要查找的目标值。
     * @return 如果找到目标值则返回 true，否则返回 false。
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // 获取矩阵的行数和列数
        int m = matrix.length;
        int n = matrix[0].length;
        
        // 步骤 1: 初始化指针，指向矩阵的右上角
        int i = 0;     // 行指针，从第 0 行开始
        int j = n - 1; // 列指针，从最后一列开始
        
        // 步骤 2: 循环搜索，只要指针还在矩阵范围内
        while (i < m && j >= 0) {
            // Case 1: 找到目标值
            if (matrix[i][j] == target) {
                return true;
            }
            
            // Case 2: 当前元素小于目标值
            // 说明 target 不可能在当前行，因为 matrix[i][j] 是当前行最大的
            // 排除当前行，向下移动
            if (matrix[i][j] < target) {
                i++;
            } else { // Case 3: 当前元素大于目标值
                // 说明 target 不可能在当前列，因为 matrix[i][j] 是当前列最小的
                // 排除当前列，向左移动
                j--;
            }
        }
        
        // 步骤 3: 如果循环结束仍未找到，说明目标值不存在
        return false;
    }
}

时空复杂度

时间复杂度：O(M + N)

1. 指针移动分析：
   • 算法的核心是两个指针 i 和 j 的移动。
   • 指针 i 只会单调递增（向下移动），从 0 最多移动到 m。
   • 指针 j 只会单调递减（向左移动），从 n-1 最多移动到 -1。
2. 循环次数：
   • 在 while 循环的每一次迭代中，i 或 j 至少有一个会移动。
   • i 最多移动 M 次，j 最多移动 N 次。
   • 因此，循环的总执行次数最多为 M + N 次。

综合分析：
算法的时间复杂度与行数和列数的和成线性关系，即 O(M + N)。

空间复杂度：O(1)

1. 主要存储开销：该算法直接在输入的 matrix 数组上进行查找，没有创建任何新的、与输入规模 M 或 N 成比例的数据结构。
2. 辅助变量：只使用了 m, n, i, j, target 等几个常数数量的变量。

综合分析：
算法所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。这是一个空间效率极高的原地算法。

参考灵神