当前位置：首页 > article >正文

leetcode74:搜索二维矩阵

article 2024/12/23 16:33:13

原题地址：74. 搜索二维矩阵 - 力扣（LeetCode）

题目描述

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

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

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

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

解题思路

题目要求在一个二维矩阵中查找一个目标值，矩阵满足以下特性：

每一行中的整数从左到右按升序排列。
每一行的第一个整数大于上一行的最后一个整数。

解题可以分两步：

确定目标所在的行：
- 使用二分查找在第一列中查找，确定目标可能所在的行索引。
- 如果目标值小于第一行的第一个元素或大于最后一行的第一个元素，返回 false。
在该行中查找目标值：
- 在确定的行中再用一次二分查找，查看目标值是否存在。

这种方法利用了矩阵的有序性，避免了直接遍历整个矩阵，时间复杂度更低。

源码实现

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 使用二分查找第一列，找到目标值可能存在的行索引
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) { // 如果返回的行索引小于0，说明目标值不在矩阵中
            return false;
        }
        // 在找到的行中再次使用二分查找，确认目标值是否存在
        return binarySearchRow(matrix[rowIndex], target);
    }

    // 在矩阵的第一列中使用二分查找，返回目标值可能存在的行索引
    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1; // 初始化low为-1，high为最后一行索引
        while (low < high) {
            // 防止溢出的写法，计算中点位置
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) { // 如果当前行的第一个元素小于或等于目标值
                low = mid; // 目标值可能在该行或更低的行
            } else {
                high = mid - 1; // 向上搜索
            }
        }
        return low; // 返回目标值可能存在的行索引
    }

    // 在给定行中使用二分查找，判断目标值是否存在
    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1; // 初始化low为0，high为行的最后一个元素索引
        while (low <= high) {
            int mid = (high - low) / 2 + low; // 防止溢出的写法
            if (row[mid] == target) { // 如果中间值等于目标值
                return true; // 找到目标值
            } else if (row[mid] > target) { // 如果中间值大于目标值
                high = mid - 1; // 向左搜索
            } else { // 如果中间值小于目标值
                low = mid + 1; // 向右搜索
            }
        }
        return false; // 未找到目标值
    }
}

复杂度分析

时间复杂度：
- 第一步（二分查找第一列）：
  - 矩阵有 m 行，查找第一列的时间复杂度为 O(log m)。
- 第二步（二分查找一行）：
  - 每行有 n 列，查找该行的时间复杂度为 O(log n)。
- 总时间复杂度：O(log m + log n)，可以简化为 O(log (m * n))。
空间复杂度：
- 算法使用了常数级的额外空间，没有开辟新的数据结构。
- 空间复杂度为 O(1)