【LeetCode热题100】74. 搜索二维矩阵(二分)

一.题目要求

给你一个满足下述两条属性的 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

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

四.解题思路

解法1:先对每列第一个元素二分,再二分查找符合条件的某一行。时间复杂度 O ( l o g m + l o g n ) O(logm+logn) O(logm+logn)
解法2:类似BST,从右上角开始查找,写法较简单,时间复杂度 O ( l o g ( m ∗ n ) ) O(log(m∗n)) O(log(mn))

五.代码实现

解2:

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int row = matrix.size();int col = matrix[0].size();for (int i = 0, j = col - 1; i < row && j >= 0;matrix[i][j] > target ? j-- : i++) {if (matrix[i][j] == target)return true;}return false;}
};

解1:

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int rowl = 0;int rowr = matrix.size() - 1;int rowmid = (rowl + rowr) / 2;while (rowl <= rowr) {rowmid = (rowl + rowr) / 2;if (matrix[rowmid][0] == target)return true;if (matrix[rowmid][0] > target) {rowr -= 1;}else if (matrix[rowmid][0] < target) {rowl += 1;}}int l = 0;int r = matrix[0].size() - 1;int m = (l + r) / 2;int row;if (rowl > rowr)row = rowr;elserow = rowl;if (row < 0 || row >= matrix.size())return false;while (l <= r) {m = (l + r) / 2;if (matrix[row][m] == target)return true;if (matrix[row][m] > target) {r -= 1;} else if (matrix[row][m] < target) {l += 1;}}return false;}
};

六.题目总结

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/300716.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

特别详细的Spring Cloud 系列教程1:服务注册中心Eureka的启动

Eureka已经被Spring Cloud继承在其子项目spring-cloud-netflix中&#xff0c;搭建Eureka Server的方式还是非常简单的。只需要通过一个独立的maven工程即可搭建Eureka Server。 我们引入spring cloud的依赖和eureka的依赖。 <dependencyManagement><!-- spring clo…

CentOS7.9.2009安装elasticsearch7.11.1(单节点)

本文章使用CentOS7.9.2009服务器安装elasticsearch7.11.1软件 1.服务器信息 [root@elasticsearch ~]# cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core) [root@elasticsearch ~]# [root@elasticsearch ~]# cat /etc/hosts | grep elasticsearch 192.168.10.24…

【MacBook系统homebrew镜像记录】

安装 使用Homebrew 国内源安装脚本,贼方便&#xff1a; /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"切换至清华大学镜像源&#xff1a; 命令合并&#xff1a; 分别切换了 brew.git、 homebrew-core.git、 homebrew-…

windows一键休眠,一键唤醒

1.使windows睡眠不可用&#xff0c;cmd以管理员身份运行&#xff1a; powercfg.exe /hibernate off 2.桌面创建快捷键 Rundll32.exe Powrprof.dll,SetSuspendState Sleep

探索7个MAMP本地开发环境的高效替代软件

什么是本地开发环境 本地开发环境是Web开发环境中的一种类型&#xff0c;它是指开发者自己的计算机上配置的一套用于开发和测试网站或应用程序的软件集合。这套环境使得开发者可以在本地计算机上构建和测试网站&#xff0c;而无需实时部署到服务器。 创建本地开发环境有两种方…

ubuntu系统安装k8s1.28精简步骤

目录 一、规划二、环境准备2.1 配置apt仓库配置系统基本软件仓库配置k8s软件仓库安装常用软件包 2.2 修改静态ip、ntp时间同步、主机名、hosts文件、主机免密2.3 内核配置2.4 关闭防火墙、selinux、swap2.5 安装软件安装docker安装containerd安装k8s软件包 三、安装配置k8s3.1 …

文本识别 OCR 解决方案

Capture2Text 便携式 OCR 工具 Capture2Text 能够使用键盘快捷键快速对屏幕的一部分进行 OCR。 默认情况下&#xff0c;生成的文本将保存到剪贴板。支持中文、英文、法文、德文、日文、韩文、俄文、西班牙文等 90 多种语言。 Capture2Text 是便携式工具&#xff0c;不需要安装…

【单源最短路 图论】882. 细分图中的可到达节点

作者推荐 视频算法专题 本文涉及知识点 单源最短路 图论 LeetCode 882. 细分图中的可到达节点 给你一个无向图&#xff08;原始图&#xff09;&#xff0c;图中有 n 个节点&#xff0c;编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链&#xff0c;每条边之间…

编程杂谈-代码review

目录 1. 关于智商 2. 关于能力 3. 关于changelist 3.1 关于CL内容编写 3.2 关于CL的大小 3.3 处理审稿人的意见 4. 关于代码审查 一个人的编程能力怎么去衡量&#xff1f;特别是在面试中&#xff0c;怎么避免“高分低能儿”、“专业做题家”、“面试造火箭”&#xff0c…

【JavaEE】_Spring MVC项目获取Session

目录 1. 使用servlet原生方法获取Session 1.1 错误获取方法 1.2 正确获取方法 2. 使用Spring注解获取Session 3. 使用Spring内置对象获取Session 1. 使用servlet原生方法获取Session .java文件内容如下&#xff1a; setSession方法用于设置Session对象的内容&#xff1b;…

LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】

LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】 题目描述&#xff1a;解题思路一&#xff1a;先二分查找行&#xff0c;再二分查找列。解题思路二&#xff1a;暴力遍历&#xff0c;也能过。解题思路三&#xff1a;用python的in。 题目描述&#xff1a; 给你一个满足下述两条…

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之四 简单视频倒放效果

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之四 简单视频倒放效果 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之四 简单视频倒放效果 一、简单介绍 二、简单视频倒放效果实现原理 三、简单视频倒放效果案例实现…

切比雪夫窗函数

Skip to content 产品解决方案学术支持社区活动 获取 MATLAB登录到您的 MathWorks 帐户 Help Center 搜索帮助中心 帮助中心 Off-Canvas Navigation Menu Toggle Documentation Home Signal Processing Signal Processing ToolboxSpectral AnalysisWindows chebwinON…

JetBrains IDE 2024.1 发布 - 开发者工具

JetBrains IDE 2024.1 (macOS, Linux, Windows) - 开发者工具 CLion, DataGrip, DataSpell, Fleet, GoLand, IntelliJ IDEA, PhpStorm, PyCharm, Rider, RubyMine, WebStorm 请访问原文链接&#xff1a;JetBrains IDE 2024.1 (macOS, Linux, Windows) - 开发者工具&#xff0…

51单片机里面的白盒测试中

白盒测试说直白点就是&#xff0c;加入一个盒子&#xff08;中间模块&#xff09;&#xff0c;使得测试的数据可视化&#xff0c;知道是内部是怎么运作的 场景&#xff1a;51单片机与WIFI模块通信&#xff0c;不能知道他们之间到底发没发数据&#xff0c;所以引出白盒测试 测试…

前端组件化探索:打造创意Canvas绘图小程序的关键技术与实现

摘要 在前端开发领域&#xff0c;Canvas 绘图已经成为了实现用户交互和视觉展示的重要手段。尤其在移动应用和小程序开发中&#xff0c;Canvas 的应用更为广泛。本文将结合一个实际的创意绘图小程序项目&#xff0c;探讨前端组件化技术在实现绘图功能中的关键作用&#xff0c;…

网络基础知识入门

目录 一、局域网与广域网 1、局域网 2、广域网 二、协议 1、概念 2、协议的理解 3、协议的分层 1、分层 2、OSI七层模型 三、网络传输基本流程 1、报头 2、局域网通信原理 3、跨网络传输流程 四、IP地址和MAC地址 1、IP地址 2、MAC地址 3、两者的区别 一、局域…

C语言 文件函数

目录 1. 文件的打开和关闭 2. 文件的顺序读写 2.1 顺序读写函数介绍 2.2读文件&#xff08;读文件只能读一次&#xff09; 2.3写文件 3. 文件的随机读写 3.1 fseek 3.2 ftell 3.3 rewind 4.文件读取结束的判定 4.1 被错误使误的 feof 我对读写的理解&#xff1a;(从…

Svg Flow Editor 原生svg流程图编辑器(五)

系列文章 Svg Flow Editor 原生svg流程图编辑器&#xff08;一&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;二&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;三&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;四&#xf…

2014最新AI智能创作系统ChatGPT网站源码,Midjourney绘画网站源码,附搭建部署教程

一、系统前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持…