【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.…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
