武汉大墨迹试试网站开发_广州代办营业执照的正规公司_关键词推广方法_广告推广免费发布

原题地址：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

解题思路

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

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

解题可以分两步：

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

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

源码实现

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; // 未找到目标值}
}

复杂度分析

1. 时间复杂度：

   • 第一步（二分查找第一列）：
     • 矩阵有 m 行，查找第一列的时间复杂度为 O(log m)。
   • 第二步（二分查找一行）：
     • 每行有 n 列，查找该行的时间复杂度为 O(log n)。
   • 总时间复杂度：O(log m + log n)，可以简化为 O(log (m * n))。

2. 空间复杂度：

   • 算法使用了常数级的额外空间，没有开辟新的数据结构。
   • 空间复杂度为 O(1)