74 搜索二维矩阵

一、题目

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

二、题解

方法一：二维转一维 + 二分查找

思路：二分查找。

1. 核心思路

由于题目保证：

  • 每一行从左到右递增；
  • 当前行第一个元素大于上一行最后一个元素；

所以整个二维矩阵可以看成一个整体有序的一维数组。

例如：

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

可以看成：

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

核心思想是：

  • 把二维矩阵当成一个长度为 m * n 的一维数组；
  • 对这个一维数组做二分查找；
  • 通过一维下标 mid 计算出它在二维矩阵中的位置。

2. 具体步骤

  1. 获取矩阵行数 m 和列数 n。
  2. 定义二分查找区间：
    • left = 0
    • right = m * n - 1
  3. 每次取中间位置 mid。
  4. 将一维下标 mid 转换成二维坐标：
    • 行号：row = mid / n
    • 列号：col = mid % n
  5. 取出当前元素 matrix[row][col]。
  6. 如果当前元素等于 target，返回 true。
  7. 如果当前元素小于 target，说明目标值在右半部分。
  8. 如果当前元素大于 target，说明目标值在左半部分。
  9. 如果二分结束还没找到，返回 false。

3. 关键逻辑

int row = mid / n;
int col = mid % n;

int num = matrix[row][col];

解释：

  • mid 是把矩阵看成一维数组后的下标；
  • mid / n 可以得到当前元素在第几行；
  • mid % n 可以得到当前元素在第几列；
  • 这样就能用一维二分的方式访问二维矩阵中的元素。

4. 代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 1. 获取矩阵的行数和列数
        int m = matrix.length;
        int n = matrix[0].length;

        // 2. 把二维矩阵看成一个长度为 m * n 的一维数组
        int left = 0;
        int right = m * n - 1;

        // 3. 二分查找
        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 4. 将一维下标 mid 转换成二维坐标
            int row = mid / n;
            int col = mid % n;

            int num = matrix[row][col];

            if (num == target) {
                return true;
            } else if (num < target) {
                // 当前值小于 target，说明 target 在右半部分
                left = mid + 1;
            } else {
                // 当前值大于 target，说明 target 在左半部分
                right = mid - 1;
            }
        }

        // 5. 没有找到 target
        return false;
    }
}

5. 复杂度分析

时间复杂度：O(log⁡(m×n))O(\log(m \times n))

说明：矩阵一共有 m * n 个元素，对整体有序数组进行二分查找，所以时间复杂度是 O(log⁡(m×n))O(\log(m \times n))。

空间复杂度：O(1)O(1)

说明：只使用了常数个变量，没有使用额外数据结构。

方法二：先二分找行，再二分找列

思路：二分查找。

1. 核心思路

方法一是把整个矩阵看成一维数组，直接做一次二分。

方法二是分两步处理：

  • 先确定 target 可能在哪一行；
  • 再在这一行中进行二分查找。

因为每一行都是有序的，并且下一行第一个元素大于上一行最后一个元素，所以对于某一行来说：

matrix[row][0] <= target <= matrix[row][n - 1]

如果这个条件成立，说明 target 只可能出现在这一行。

这种方法的核心是：

  • 先用二分查找定位可能的行；
  • 再在这一行内用二分查找目标值；
  • 如果找不到，说明矩阵中不存在 target。

2. 具体步骤

  1. 获取矩阵行数 m 和列数 n。
  2. 对行号进行二分查找。
  3. 每次取中间行 midRow。
  4. 判断 target 和这一行的范围关系：
    • 如果 target < matrix[midRow][0]，说明目标值在更上面的行；
    • 如果 target > matrix[midRow][n - 1]，说明目标值在更下面的行；
    • 否则说明 target 可能在当前行。
  5. 找到可能的行之后，在该行中进行普通二分查找。
  6. 如果找到 target，返回 true。
  7. 否则返回 false。

3. 关键逻辑

if (target < matrix[midRow][0]) {
    right = midRow - 1;
} else if (target > matrix[midRow][n - 1]) {
    left = midRow + 1;
} else {
    row = midRow;
    break;
}

解释：

  • 如果 target 小于当前行第一个元素，说明当前行以及下面的行都太大，需要往上找；
  • 如果 target 大于当前行最后一个元素，说明当前行以及上面的行都太小，需要往下找；
  • 否则说明 target 落在当前行的范围内，只需要在这一行里继续查找。

4. 代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 1. 获取矩阵的行数和列数
        int m = matrix.length;
        int n = matrix[0].length;

        // 2. 先二分查找 target 可能所在的行
        int left = 0;
        int right = m - 1;
        int row = -1;

        while (left <= right) {
            int midRow = left + (right - left) / 2;

            if (target < matrix[midRow][0]) {
                // target 比当前行第一个元素还小，说明应该去上面的行找
                right = midRow - 1;
            } else if (target > matrix[midRow][n - 1]) {
                // target 比当前行最后一个元素还大，说明应该去下面的行找
                left = midRow + 1;
            } else {
                // target 在当前行的范围内
                row = midRow;
                break;
            }
        }

        // 3. 如果没有找到可能的行，说明 target 不存在
        if (row == -1) {
            return false;
        }

        // 4. 在找到的这一行中继续二分查找
        left = 0;
        right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] < target) {
                // 当前值小于 target，往右找
                left = mid + 1;
            } else {
                // 当前值大于 target，往左找
                right = mid - 1;
            }
        }

        // 5. 当前行中没有找到 target
        return false;
    }
}

5. 复杂度分析

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

说明：先在 m 行中二分查找可能的行，时间复杂度是 O(log⁡m)O(\log m)；再在 n 列中二分查找目标值，时间复杂度是 O(log⁡n)O(\log n)，所以总时间复杂度是 O(log⁡m+log⁡n)O(\log m + \log n)。

空间复杂度：O(1)O(1)

说明：只使用了常数个变量，没有使用额外数据结构。

评论