【LeetCode热题100】240. 搜索二维矩阵 II
一.题目要求
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。 ‘
- 每列的元素从上到下升序排列。
二.题目难度
中等
三.输入样例
示例 1:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true
示例 2:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false
提示:
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
− 1 0 9 -10^9 −109 <= matrix[i][j] <= 1 0 9 10^9 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
− 1 0 9 -10^9 −109 <= target <= 1 0 9 10^9 109
四.解题思路
解法1.直接遍历 O ( m n ) O(mn) O(mn) 没想到能过。。
解法2.对每行(有序)所以可以二分查找 O ( m l o g 2 n ) O(mlog _2n) O(mlog2n) 。
解法3.Z型查找 O ( m + n ) O(m+n) O(m+n) 没想到还能这么玩 GPT解释如下:
利用矩阵的两个属性:每行的元素从左到右升序排列,每列的元素从上到下升序排列。基于这两个属性,可以从矩阵的右上角(或左下角)开始搜索。
算法思路
从右上角开始搜索:
- 如果当前元素等于目标值,则返回true。 如果当前元素小于目标值,则移动到下一行(因为当前列的所有元素都将小于目标值)。
- 如果当前元素大于目标值,则移动到前一列(因为当前行的所有元素都将大于目标值)。
- 重复这些步骤,直到找到目标值或者搜索区域为空。
这种方法之所以有效,是因为它每次迭代都排除一行或一列,这样就可以在常数时间内将搜索空间减半,从而实现快速查找。
五.代码实现
Z型查找:解法3
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty()) return false;int rows = matrix.size(), cols = matrix[0].size();int row = 0, col = cols - 1; // 从右上角开始while (row < rows && col >= 0) {if (matrix[row][col] == target) {return true; // 找到目标值} else if (matrix[row][col] < target) {row++; // 移动到下一行} else {col--; // 移动到前一列}}return false; // 搜索区域为空,未找到目标值}
};
解法1
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for (vector<vector<int>>::iterator it = matrix.begin(); it != matrix.end(); it++){for (vector<int>::iterator itt = it->begin(); itt != it->end(); itt++){if (*itt == target)return true;}}return false;}
};
解法2
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for (vector<vector<int>>::iterator it = matrix.begin(); it != matrix.end(); it++){vector<int>::iterator fit = lower_bound(it->begin(), it->end(), target);if (fit != it->end() && *fit == target)return true;}return false;}
};
六.题目总结
卧室撒币
相关文章:
【LeetCode热题100】240. 搜索二维矩阵 II
一.题目要求 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。 ‘每列的元素从上到下升序排列。 二.题目难度 中等 三.输入样例 示例 1: 输入:matrix [[1,4,7…...
three.js 鼠标左右拖动改变玩家视角
这里主要用到了 一个方法 obj.getWorldDirection(); obj.getWorldDirection()表示的获取obj对象自身z轴正方向在世界坐标空间中的方向。 按下 W键前进运动; <template><div><el-container><el-main><div class"box-card-left…...
Pycharm jupyter server process exited with code 1
Pycharm jupyter server process exited with code 1 1. 问题描述2. 原因和解决方法 1. 问题描述 使用 Pycharm 启动 Jupyter 时,报错如下, jupyter server process exited with code 12. 原因和解决方法 Pycharm 启动 jupyter 时,默认的 …...
ubuntu 20.04 Python pip 配置 pip.conf
1. 状况描述 $ pip install timm WARNING: Retrying (Retry(total4, connectNone, readNone, redirectNone, statusNone)) after connection broken by ProxyError(Cannot connect to proxy., RemoteDisconnected(Remote end closed connection without response)): /simple/t…...
GPT-4.5 Turbo意外曝光,最快明天发布?OpenAI终于要放大招了!
大家好,我是木易,一个持续关注AI领域的互联网技术产品经理,国内Top2本科,美国Top10 CS研究生,MBA。我坚信AI是普通人变强的“外挂”,所以创建了“AI信息Gap”这个公众号,专注于分享AI全维度知识…...
Ubuntu 中 desktop-amd64 和 live-server-amd64 的区别
一、Ubuntu的操作系统镜像 Ubuntu的操作系统镜像主要有两种:desktop-amd64和live-server-amd64 这两者的主要区别在于使用场景和安装方式 1. Desktop-amd64: * 这是Ubuntu的桌面版本,用于安装具有图形用户界面的Ubuntu系统。 * 它包含了用于日常使…...
第10集《天台教观纲宗》
请大家打开讲义第十七页。我们讲到己二、结申正义。 己二、结申正义 《法华经》把我们修行人修行的相貌,比喻作一个车乘。车乘就是一种交通工具,它能够让我们从此岸超越到彼岸去。所以修行它是可以超越的,你今天比昨天超越了,就好…...
每日学习笔记:C++ STL 的forward_list
定义 特点 操作函数 元素查找、移除或安插 forward_list::emplace_after arg...指的是元素构造函数的参数(0~N个) #include <iostream> #include <memory> #include <list> #include <forward_list> using namespace std;class…...
【Java,Redis】Redis 数据库存取字符串数据以及类数据
1、 字符串存取数据 Resource private StringRedisTemplate stringRedisTemplate;//从Redis中获取string字符串 stringRedisTemplate.opsForValue().get("cache:shop:"id); //Json -> class Shop shop JSONUtil.toBean(ShopJson,Shop.class); //字符串写入redis…...
OpenCV 图像重映射函数remap()实例详解
OpenCV 图像重映射函数remap()对图像应用通用几何变换。其原型如下: void remap(InputArray src, OutputArray dst, InputArray map1, InputArray map2, int interpolation, int borderMode BORDER_CONSTANT, const Scalar & borde…...
Python基础课堂最后一课23——正则对象
文章目录 前言一、正则对象是什么?二、正则表达式基本分类1.普通字符2.元字符 总结 前言 很开心能和你们一些学习进步,在这一个多月的时间中,是你们让我坚持了下来,完成了python基础课堂编写,不管如何,我们…...
【算法训练营】凸包,图(Python实现)
凸包 描述 给定n个二维平面上的点,求他们的凸包。 输入 第一行包含一个正整数n。 接下来n行,每行包含两个整数x,y,表示一个点的坐标。 输出 令所有在凸包极边上的点依次为p1,p2,...,pm(序号),其中m表…...
webpack5零基础入门-6webpack处理图片资源
1.在webpack5中file-loader和url-loader为内置模块 通过在加载器中配置rule即可激活 {test: /\.(png|jpe?g|gif|webp)$/,type: asset} 2.使用webpack进行打包 执行npx webpack 可以看到图片资源打包后都被放到了dist文件目录下 3.使用webpack进行图片格式转换为base64 优势…...
计算机基础知识QA
目录 数据库 --mysql 关联查询 唯一索引如何创建,语句 更新表字段语句 查看字段类型 --redis 使用场景 数据结构 设置超时时间 linux 常用命令 发布版本 安装一个东西,发现一个东西安装的很慢,如何切换ip地的源?-&g…...
微信小程序一次性订阅requestSubscribeMessage授权和操作详解
一次性订阅:用户订阅一次发一次通知 一、授权 — requestSubscribeMessage Taro.requestSubscribeMessage({tmplIds: [], // 需要订阅的消息模板的id的集合success (res) {console.log("同意授权", res)},fail(res) {console.log(拒绝授权, res)}})点击或…...
ARM 汇编指令:(三)运算处理指令
目录 一.add指令 二.sub指令 三.MUL指令 一.add指令 add用于执行实现两个寄存器或寄存机或寄存器与立即数的相加操作。它可以用于整数、浮点数等各种数据类型的加法运算。 ADD{cond}{S} Rd,操作数,操作数 1.不带进位加法指令add add r1, r2, #4 //r1 r2 4 add r1, r2 …...
【C++庖丁解牛】STL简介 | string容器初次见面
🍁你好,我是 RO-BERRY 📗 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 目录 1. 什么是STL2. STL的版本…...
记OnlyOffice的两个大坑
开发版,容器部署,试用许可已安装。 word,ppt,excel均能正常浏览。 自带的下载菜单按钮能用。 但config里自定义的downloadAs方法却不一而足。 word能正常下载,excel和ppt都不行。 仔细比对调试了代码。发现app.js…...
分享几个Google Chrome谷歌浏览器历史版本下载网站
使用selenium模块的时候,从官网下载的谷歌浏览器版本太高,驱动不支持,所以需要使用历史的谷歌浏览器版本 ,这里备份一下以防找不到了。 驱动下载地址:https://registry.npmmirror.com/binary.html?pathchromedriver 文…...
备考2025年AMC8竞赛:吃透2000-2024年600道真题(免费赠送真题)
我们继续来随机看五道AMC8的真题和解析,根据实践经验,对于想了解或者加AMC8美国数学竞赛的孩子来说,吃透AMC8历年真题是备考最科学、最有效的方法之一。 即使不参加AMC8竞赛,吃透了历年真题600道和背后的知识体系,那么…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
