当前位置: 首页 > news >正文

LeetCode[中等] 74.搜索二维矩阵

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

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

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

public class Solution {public bool SearchMatrix(int[][] matrix, int target) {int m = matrix.Length, n = matrix[0].Length;int low = 0, high = m * n - 1;while(low <= high){int mid = low + (high - low) / 2;int row = mid / n , column = mid % n;if(matrix[row][column] == target)return true;else if(matrix[row][column] > target)high = mid -1;elselow = mid + 1;}return false;}
}

思路:m 行 n 列的矩阵可以转换成长度为 mn 的升序数组。矩阵中的每个位置可以和升序数组中的下标转换:

  • 当 0≤i<m 且 0≤j<n 时,矩阵的第 i 行第 j 列等价于升序数组的下标 i×n+j;

  • 当 0≤index<mn 时,升序数组的下标 index 等价于矩阵的第 ⌊nindex​⌋ 行第 index mod n 列。

为了判断矩阵中是否存在目标值,可以在矩阵转换成的升序数组中二分查找。

复杂度分析

代码

测试用例

测试结果

测试结果

全部题解

74. 搜索二维矩阵

Storm

Guardian

关注

242

2022.06.11

发布于 上海

数组

二分查找

矩阵

C

6+

解法

思路和算法

由于给定的矩阵满足每行升序排序,且每行的第一个整数大于前一行的最后一个整数,因此如果将矩阵的每一行拼接到前一行的末尾,可以得到一个升序数组,m 行 n 列的矩阵可以转换成长度为 mn 的升序数组。矩阵中的每个位置可以和升序数组中的下标转换:

  • 当 0≤i<m 且 0≤j<n 时,矩阵的第 i 行第 j 列等价于升序数组的下标 i×n+j;

  • 当 0≤index<mn 时,升序数组的下标 index 等价于矩阵的第 ⌊nindex​⌋ 行第 indexmodn 列。

为了判断矩阵中是否存在目标值,可以在矩阵转换成的升序数组中二分查找。

用 low 和 high 分别表示二分查找的下标范围的下界和上界,初始时 low=0,high=mn−1。每次查找时,取 mid 为 low 和 high 的平均数向下取整,计算下标 mid 对应的矩阵行下标和列下标,判断矩阵中的相应位置的数和目标值的大小关系,调整查找的下标范围。

  • 如果矩阵中相应位置的数等于 target,则找到目标值,返回 true。

  • 如果矩阵中相应位置的数大于 target,则如果目标值存在,其下标一定小于 mid,因此在下标范围 [low,mid−1] 中继续查找。

  • 如果矩阵中相应位置的数小于 target,则如果目标值存在,其下标一定大于 mid,因此在下标范围 [mid+1,high] 中继续查找。

如果查找的过程中出现 low>high,则目标值不存在,返回 false。

代码

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = low + (high - low) / 2;int row = mid / n, column = mid % n;if (matrix[row][column] == target) {return true;} else if (matrix[row][column] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}

复杂度分析

  • 时间复杂度:O(log(mn)),其中 m 和 n 分别是矩阵 matrix 的行数和列数。矩阵中的元素个数是 mn,二分查找的次数是 O(log(mn)),每次查找的时间是 O(1),时间复杂度是 O(log(mn))。

  • 空间复杂度:O(1)。

http://www.lryc.cn/news/442969.html

相关文章:

  • overleaf如何下载论文的pdf
  • Java 每日一刊(第13期):this super static
  • 关于一些Spring的配置的作用
  • 利用Python与Ansible实现高效网络配置管理
  • JDBC技术在不同数据库系统中的兼容性及Java数据库交互技术概览
  • 双击热备 Electron网页客户端
  • 数据中台系统产品原型RP原型Axure高保真交互原型 源文件分享
  • 论文阅读笔记:Sapiens: Foundation for Human Vision Models
  • 【学术会议:中国厦门,为全球的计算机科学与管理科技研究者提供一个国际交流平台】第五届计算机科学与管理科技国际学术会议(ICCSMT 2024)
  • RK3588/RK3588s运行yolov8达到27ms
  • 2024年华为杯中国研究生数学建模竞赛E题(高速公路应急车道紧急启用模型)思路
  • np.random.seed设完又想用随机seed怎么办
  • [数据结构]动态顺序表的实现与应用
  • Invalid Private Key, Not a valid string or uint8Array
  • 【Text2SQL】PET-SQL:在Spider基准测试中取得了SOTA
  • python-3n+1数链/233
  • vue2基础系列教程之v-model及面试高频问题
  • 【高分系列卫星简介——高分一号(GF-1)】
  • Python基于TensorFlow实现时间序列循环神经网络回归模型(LSTM时间序列回归算法)项目实战
  • springboot实战学习(6)(用户模块的登录认证)(初识令牌)(JWT)
  • 二叉树的顺序存储和基本操作实现
  • python学习-10【模块】
  • modbus调试助手/mqtt调试工具/超轻巧物联网组件/多线程实时采集/各种协议支持
  • 数值计算 --- 平方根倒数快速算法(0x5f3759df,这是什么鬼!!!)
  • 迭代器和生成器的学习笔记
  • ES5 在 Web 上的现状
  • 人话学Python-循环语句
  • 初识模版!!
  • 算法之数学--hash算法 2021-03-11(未完待续)
  • DHCP工作原理