240. 搜索二维矩阵

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。

矩阵具有以下特性：

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

---

示例

示例 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

---

解题思路

1. 为什么可以用特殊的方法搜索？

由于矩阵的特点：

• 行是升序排列：左边的数小于右边的数。
• 列是升序排列：上面的数小于下面的数。

我们可以利用矩阵的这种性质，将搜索范围逐步缩小，而无需遍历整个矩阵。

2. 选择从右上角开始搜索

• 从右上角出发（matrix[0][n-1]），有以下特性：
  • 如果当前值比目标值 target 小，那么目标值一定在当前值的下面 → 行号增加。
  • 如果当前值比目标值 target 大，那么目标值一定在当前值的左边 → 列号减少。
  • 如果当前值等于 target，直接返回 true。

3. 为什么从右上角而不是左下角？

从左下角出发也可以完成搜索：

• 当前值比目标值小时，向右移动 → 列号增加。
• 当前值比目标值大时，向上移动 → 行号减少。

但从右上角搜索更加直观，便于理解和实现。

4. 为什么这个方法高效？

每次移动要么向下移动一行，要么向左移动一列，总共最多移动 m + n 步，因此时间复杂度为 ( O(m + n) )。

---

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read matrix dimensions
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // Read matrix elements
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        // Read target value
        int target = scanner.nextInt();

        Solution solution = new Solution();
        boolean result = solution.searchMatrix(matrix, target);

        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int row = 0;       // 从第一行开始
        int col = cols - 1; // 从最后一列开始

        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return true; // 找到目标值
            } else if (matrix[row][col] > target) {
                col--; // 当前值比目标值大，向左移动
            } else {
                row++; // 当前值比目标值小，向下移动
            }
        }

        return false; // 遍历结束后仍未找到目标值
    }
}

---

代码详解

1. 初始边界设置：

   • 从右上角的元素开始：row = 0, col = cols - 1。

2. 移动规则：

   • 如果当前值大于 target，向左移动，缩小列范围。
   • 如果当前值小于 target，向下移动，缩小行范围。
   • 如果当前值等于 target，直接返回 true。

3. 边界条件：

   • 当 row >= rows 或 col < 0 时，说明搜索范围已经超出矩阵边界，返回 false。

---

时间复杂度分析

1. 搜索路径：
   • 从右上角开始，每次移动要么向左（列号减1），要么向下（行号加1）。
   • 最坏情况下，需要遍历一条完整的路径：从右上角到左下角。
   • 最大移动次数为 m + n - 1 次。

总时间复杂度：O(m + n)，其中 m 是矩阵行数，n 是矩阵列数。

---

空间复杂度分析

1. 原地搜索：
   • 不使用额外的数据结构存储矩阵信息。
2. 辅助变量：
   • 仅使用行号、列号等常数个变量。

总空间复杂度：O(1)，常数空间复杂度。

---

测试用例和边界情况

• 普通测试用例：

  • matrix = [[1, 4, 7], [2, 5, 8], [3, 6, 9]], target = 6 → 输出 true
  • matrix = [[1, 4, 7], [2, 5, 8], [3, 6, 9]], target = 10 → 输出 false

• 特殊边界用例：

  • 空矩阵：matrix = [], target = 1 → 输出 false
  • 只有一行：matrix = [[1, 2, 3]], target = 2 → 输出 true
  • 只有一列：matrix = [[1], [2], [3]], target = 4 → 输出 false

---