【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(m∗n))
五.代码实现
解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;}
};
六.题目总结
–
相关文章:
【LeetCode热题100】74. 搜索二维矩阵(二分)
一.题目要求 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,…...
Android OkHttp
目录 1.build.gradle 2.基本使用 3.POST请求 4.Builder构建者 1.build.gradle implementation("com.squareup.okhttp3:okhttp:4.12.0") 2.基本使用 GET同步请求 public void getSync(View view) {new Thread(){Overridepublic void run() {Request request …...
Java常用API_正则表达式_字符串的替换和截取方法——小练习
我将通过一个练习题来展示这两个方法 练习题: 有一段字符串:小张qwertyuiop123小李asdfghjkl456小王 要求1:把字符串中三个姓名之间的字母替换成vs 要求2:把字符串中的三个姓名切割出来 编写代码: public class Tes…...
从头开发一个RISC-V的操作系统(四)嵌入式开发介绍
文章目录 前提嵌入式开发交叉编译GDB调试,QEMU,MAKEFILE练习 目标:通过这一个系列课程的学习,开发出一个简易的在RISC-V指令集架构上运行的操作系统。 前提 这个系列的大部分文章和知识来自于:[完结] 循序渐进&#x…...
Web漏洞-文件上传常见验证
后缀名:类型,文件头等 后缀名:黑白名单 文件类型:MIME信息 文件头:内容头信息 常见黑名单(明确不允许上传的格式后缀):asp、php、jsp、aspx、cgi、war (如果没有完整…...
如何在 Node.js 中使用 bcrypt 对密码进行哈希处理
在网页开发领域中,安全性至关重要,特别是涉及到用户凭据如密码时。在网页开发中至关重要的一个安全程序是密码哈希处理。 密码哈希处理确保明文密码在数据库受到攻击时也难以被攻击者找到。但并非所有的哈希方法都是一样的,这就是 bcrypt 突…...
嵌入式学习49-单片机2
指令周期 1M 机器周期 12M (晶体震荡器产生) 中断两种方式 …...
汽车EDI:如何与奔驰建立EDI连接?
梅赛德斯-奔驰是世界闻名的豪华汽车品牌,无论是技术实力还是历史底蕴都在全球汽车主机厂中居于领先位置。奔驰拥有多种车型,多元化的产品布局不仅满足了不同用户画像的需求,也对其供应链体系有着极大的考验。 本文将为大家介绍梅赛德斯-奔驰乘…...
性能分析--内存知识
内存相关知识 计算机中与CPU进行数据交换的桥梁。内存的速度,比CPU的速度要慢很多。比磁盘速度要快很多。内存中存放数据,一旦断电就会消失。linux系统的 /proc路径下的文件,都是内存文件。内存大小,一般 是GB为单位。 现在都操作…...
目标检测标签分配策略,难样本挖掘策略
在目标检测任务中,样本的划分对于模型的性能具有至关重要的影响。其中,正样本指的是包含目标物体的图像或区域,而负样本则是不包含目标物体的图像或区域。然而,在负样本中,有一部分样本由于其与正样本在特征上的相似性…...
Java | Leetcode Java题解之第16题最接近的三数之和
题目: 题解: class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int n nums.length;int best 10000000;// 枚举 afor (int i 0; i < n; i) {// 保证和上一次枚举的元素不相等if (i > 0 && nums…...
FIN和RST的区别,几种TCP连接出现RST的情况
一、RST跟FIN的区别: 正常关闭连接的时候发的包是FIN,但是如果是异常关闭连接,则发送RST包 两者的区别在于: 1.RST不必等缓冲区的包都发出去,直接就丢弃缓存区的包发送RST包。而FIN需要先处理完缓存区的包才能发送F…...
2024/4/1—力扣—删除字符使频率相同
代码实现: 思路: 步骤一:统计各字母出现频率 步骤二:频率从高到低排序,形成频率数组 步骤三:频率数组只有如下组合符合要求: 1, 0...0n 1, n...n (, 0)n...n, 1(, 0) bool equalFrequency(char…...
Spring源码解析-容器基本实现
spring源码解析 整体架构 defaultListableBeanFactory xmlBeanDefinitionReader 创建XmlBeanFactory 对资源文件进行加载–Resource 利用LoadBeandefinitions(resource)方法加载配置中的bean loadBeandefinitions加载步骤 doLoadBeanDefinition xml配置模式 validationMode 获…...
Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之四 简单视频倒放效果
Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之四 简单视频倒放效果 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之四 简单视频倒放效果 一、简单介绍 二、简单视频倒放效果实现原理 三、简单视频倒放效果案例实现…...
蓝牙学习十(扫描)
一、简介 从之前的文章中我们知道,蓝牙GAP层定义了四种角色,广播者(Broadcaster)、观察者(Observer)、外围设备(Peripheral)、中央设备(Central)。 之前的学习…...
(26)4.7 字符函数和字符串函数
#include<stdio.h> #include<string.h> #include<assert.h> //int my_strcmp(const char* str1, const char* str2) //{ // assert(str1 && str2);//指针有效性,不能为空指针 // while (*str1 *str2) // { // if (*str1…...
交换机与队列的简介
1.流程 首先先介绍一个简单的一个消息推送到接收的流程,提供一个简单的图 黄色的圈圈就是我们的消息推送服务,将消息推送到 中间方框里面也就是 rabbitMq的服务器,然后经过服务器里面的交换机、队列等各种关系(后面会详细讲&…...
1.docker
Docker 是一种容器化平台,可以在不同的操作系统中轻松运行和管理应用程序。它使用容器技术来打包应用程序及其所有依赖关系,使其可以在任何环境中运行。 Docker 的基本概念包括以下几个部分: 镜像(Image):…...
ThinkPHP审计(2) Thinkphp反序列化链5.1.X原理分析从0编写POC
ThinkPHP审计(2) Thinkphp反序列化链子5.1.X原理分析&从0编写POC 文章目录 ThinkPHP审计(2) Thinkphp反序列化链子5.1.X原理分析&从0编写POC动态调试环境配置Thinkphp反序列化链5.1.X原理分析一.实现任意文件删除二.实现任意命令执行真正的难点 Thinkphp反序列化链5.1.…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
