Loading...
墨滴

SuperMP

2021/04/20  阅读:44  主题:默认主题

Leetcode刷题 | 第112题:搜索二维矩阵

为你战死是我至高无上的荣耀。

74. 搜索二维矩阵[1]

题目:编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列;
  • 每行的第一个整数大于前一行的最后一个整数。
示例:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false

提示:
m == matrix.length, n == matrix[i].length
1 <= m, n <= 100, -10^4 <= matrix[i][j], target <= 10^4

对于有序数组的目标值搜索,可以使用二分查找(Binary Search)来完成,其时间复杂度为 O(log N),其中 N 为数组的长度。

分析:观察上述矩阵,若将其展开,则为升序的“数组”。在不展开的情况下,矩阵的任意行 / 列都是一个有序的“数组”,因此可以使用两次二分查找完成对 target 值的搜索:

  1. 以最后一列为基础,搜索 target 值处于矩阵的哪一行;
  2. 确定 target 值所处的行索引后,对该行进行二分搜索,确定 target 值是否存在。

Java代码:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (target < matrix[0][0] || target > matrix[m - 1][n - 1]) return false;

        int up = 0, down = m - 1, mid;
        while (up < down) { // 上下二分搜索, 确定target在哪一行
            mid = up + (down - up) / 2;
            if (matrix[mid][n - 1] > target) {
                down = mid;
            } else if (matrix[mid][n - 1] < target) {
                up = mid + 1;
            } else {
                return true;
            }
        }

        int left = 0, right = n - 1;
        while (left <= right) { // 左右二分搜索, 确定target是否存在
            mid = left + (right - left) / 2;
            if (matrix[up][mid] > target) {
                right = mid - 1;
            } else if (matrix[up][mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
  • 时间复杂度为 O(log m + log n) = O(log mn),空间复杂度为 O(1)。

参考资料

[1]

搜索二维矩阵: https://leetcode-cn.com/problems/search-a-2d-matrix/

SuperMP

2021/04/20  阅读:44  主题:默认主题

作者介绍

SuperMP