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

力扣(LeetCode)240. 搜索二维矩阵 II(C++)

题目描述dd

枚举

枚举整个矩阵,找到等于 target 的元素,则 return true ,否则 return false

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n = matrix.size(), m = matrix[0].size();for (auto &x : matrix)for (auto &t : x)if (t == target) return true;return false;}
};
  1. 时间复杂度 : O(n×m)O(n\times m)O(n×m)nnn 是数组的行数,mmm 是数组的列数,枚举所有元素,时间复杂度 O(n×m)O(n\times m)O(n×m)
  2. 空间复杂度 : O(1)O(1)O(1) , 只使用常量级空间 。

二分查找

二分优化枚举。按行枚举矩阵,由于每行元素有序,可以二分查找行内的元素。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n = matrix.size(), m = matrix[0].size();for (auto &x : matrix) {int l = 0, r = m - 1;while(l <= r) {int mid = l + (r - l >> 1);if (x[mid] < target) l = mid + 1;else r = mid - 1;}if (l < m && x[l] == target) return true;}return false;}
};
  1. 时间复杂度 : O(nlogm)O(nlogm)O(nlogm)nnn 是数组的行数,mmm 是数组的列数,一次枚举一行,每行二分查找,时间复杂度 O(nlogm)O(nlogm)O(nlogm)
  2. 空间复杂度 : O(1)O(1)O(1) , 只使用常量级空间 。

枚举行列

更大胆的,同时枚举行列。这是由于每行元素有序,每列元素同样有序。

目的:保证被枚举元素与 target 的大小关系,对应唯一的移动方向

结论:从右上角枚举到左下角,根据右上角元素与 target 的大小关系,确定枚举的移动方向。

证明:右上角元素是一行的最大元素,一列的最小元素。往左下枚举,要找比他小的元素,只能同行往左;要找比他大的元素,只能同列向下。即
右上角元素 >\gt> target,往左;右上角元素 <\lt< target,往下。

朴素错法
  • 为什么从左上角枚举到右下角不行?
    答:左上角元素是一行的最小元素,一列的最小元素。往右下枚举,要找比他大的元素,不能确定往右还是往下。
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n = matrix.size(), m = matrix[0].size();int i = 0, j = m - 1;while(i < n && j >= 0) {if (matrix[i][j] > target) j --;else if (matrix[i][j] < target) i ++;else return true;}return false;}
};
  1. 时间复杂度 : O(n+m)O(n+m)O(n+m)nnn 是数组的行数,mmm 是数组的列数,一次枚举,移动一列或者一行,时间复杂度 O(n+m)O(n+m)O(n+m)
  2. 空间复杂度 : O(1)O(1)O(1) , 只使用常量级空间 。

AC

按行列枚举,执行结果。

AC

致语

  • 理解思路很重要
  • 读者有问题请留言,清墨看到就会回复的。

相关文章:

力扣(LeetCode)240. 搜索二维矩阵 II(C++)

题目描述 枚举 枚举整个矩阵&#xff0c;找到等于 target 的元素&#xff0c;则 return true &#xff0c;否则 return false。 class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n matrix.size(), m matrix[0]…...

golang defer

文章目录延迟函数的参数在defer语句出现时就已经确定下来了延迟函数没有入参时&#xff0c;延迟函数体内的变量会受到影响延迟函数 *可以* 修改主函数的 *具名* 返回值延迟函数 *无法* 修改主函数的 *匿名* 返回值defer会把声明的 延迟函数以及 函数的入参放到栈上&#xff0c;…...

【Java】线程的死锁和释放锁

线程死锁是线程同步的时候可能出现的一种问题 文章目录1. 线程的死锁1.1 基本介绍1.2 应用案例2. 释放锁2.1 下面的操作会释放锁2.2 下面的操作不会释放锁1. 线程的死锁 1.1 基本介绍 多个线程都占用了对方的锁资源&#xff0c;但不肯相让&#xff0c;导致了死锁&#xff0c;…...

如何使用断点续传上传大文件

概念 大文件上传的需求介绍 不管怎样简单的需求&#xff0c;在量级达到一定层次时&#xff0c;都会变得异常复杂。 文件上传简单&#xff0c;文件变大就复杂 上传大文件时&#xff0c;以下几个变量会影响我们的用户体验 服务器处理数据的能力请求超时网络波动 上传时间会变长…...

【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波

【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波 文章目录【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波1. 前言2. 符号说明3. 三种滤波3.1 全通滤波3.2 低通滤波3.2.1 平滑信号分析3.2.2 广义拉普拉斯平滑滤波器3.3 高通滤波4. 总结1. 前言 GCN&…...

python操作mysql数据库详解

使用Python操作MySQL数据库 MySQL是一种关系型数据库管理系统&#xff0c;它可以用来存储和管理大量的数据。之前介绍了大部分主流数据库&#xff0c;今天将介绍如何使用Python来操作MySQL数据库。 安装MySQL 首先&#xff0c;我们需要安装MySQL服务器&#xff0c;可以从MyS…...

netty群聊系统

1设计思路&#xff1a;启动一个服务端&#xff0c;多个客户端第一个客户端启动时&#xff0c;会告诉服务器上线了第二个客户端启动时&#xff0c;告诉服务器上线&#xff0c;并且通知第一个启动的客户端第三个客户端启动时&#xff0c;告诉服务器上线&#xff0c;并且通知第一个…...

Android 初代 K-V 存储框架 SharedPreferences,旧时代的余晖?

本文已收录到 AndroidFamily&#xff0c;技术和职场问题&#xff0c;请关注公众号 [彭旭锐] 提问。 前言 大家好&#xff0c;我是小彭。 SharedPreferences 是 Android 平台上轻量级的 K-V 存储框架&#xff0c;亦是初代 K-V 存储框架&#xff0c;至今被很多应用沿用。 有的…...

在windows中使用tomcat搭建Jenkins

1、 准备环境&#xff1a;JDK JDK官网下载&#xff1a;https://download.oracle.com/java/19/latest/jdk-19_windows-x64_bin.msi 2、 tomcat包 tocat官网下载&#xff1a;https://tomcat.apache.org/download-90.cgi 3、 Jenkins.war包 Jenkins官网下载&#xff1a;https://mi…...

Linux系统

linux系统 世界上最重要的服务器端操作系统。 创建新目录 mkdir app mkdir -m 目录权限 目录名 创建有权限的目录名。 创建一个空白文件 touch app.txt创建一个文件。 cat创建一个文件。 vi/vim创建一个文件。 nano创建一个文件。 truncate创建一个文件。 pwd查看当前目录。 rm…...

Mel Frequency Cepstral Coefficients (MFCCs)

wiki里说 在声音处理中&#xff0c;梅尔频率倒谱( MFC ) 是声音的短期功率谱的表示&#xff0c;基于非线性梅尔频率标度上的对数功率谱的线性余弦变换。 倒谱和MFC 之间的区别在于&#xff0c;在 MFC 中&#xff0c;频带在梅尔尺度上等距分布&#xff0c;这比正常频谱中使用的线…...

第七讲---贪心(上课)

1.股票买卖 一、贪心 考虑一种方案&#xff0c;在每次上升的前一天购入股票&#xff0c;并在上升后的当天卖出的方案 if (w[i] > w[i - 1])res w[i] - w[i - 1];接下来证明该贪心思路得出的方案即是最优解。 &#xff08;1&#xff09;证明贪心解 ≥ 最优解&#xff1a; …...

计算机如何思考与图灵完备

图灵完备是针对一套数据操作规则而言的概念,数据操作规则可以是一门编程语言,也可以是计算机实现里面的指令集,比如C/C++是图图灵完备的,通用CPU也是图灵完备的,但是GPU却不一定是图灵完备的。说白了图灵完备定义了一套规则,当这套规则可以实现图灵迹模型里的全部功能时,…...

惠普LaserJet M1005 MFP报错b2

故障现象: 惠普LaserJet M1005 MFP开机后直接报b2错误; 检测维修: 故障大意是:机器的硬件可能出现点突变,此问题建议联系当地维修中心进行处理。...

网络协议(TCP/IP)

目录一、网络分层模型二、OSI模型三、网络传输原理四、TCP/IP1、TCP/IP 原理2、TCP 三次握手/四次挥手3、Http协议和TCP/IP的区别五、HTTP原理六、HTTPS原理七、CDN原理一、网络分层模型 互联网的本质就是一系列的网络协议&#xff0c;最早由ISO国际组织定义为7层网络参考模型…...

2023河南省第二届职业技能大赛郑州市选拔赛“网络安全” 项目比赛样题任务书

2023河南省第二届职业技能大赛郑州市选拔赛“网络安全” 项目比赛样题任务书2023河南省第二届职业技能大赛郑州市选拔赛“网络安全” 项目比赛样题任务书A模块基础设施设置/安全加固&#xff08;200分&#xff09;A-1&#xff1a;登录安全加固&#xff08;Windows, Linux&#…...

6、流程控制

目录一、if二、switch三、for四、break与continue五、goto与Label一、if if使用&#xff1a;逻辑表达式成立&#xff0c;就会执行{}里的内容&#xff1b;逻辑表达式不需要加() if 5 > 9 {fmt.Println("5>9") }if句子中允许包含1个(仅1个)分号&#xff1a;在分…...

Linux中最基本常见命令总结

❤❤&#x1f49b;&#x1f49b;&#x1f49a;&#x1f49a;&#x1f499;&#x1f499;&#x1f49c;&#x1f49c;您的认可是对我最大的帮助&#x1f49c;&#x1f49c;&#x1f499;&#x1f499;&#x1f49a;&#x1f49a;&#x1f49b;&#x1f49b;❤❤ &#x1f90e;&…...

Python学习-----模块2.0(常用模块之时间模块-->time)

目录 前言&#xff1a; time简介 导入模块 1.时间戳 2.时间元组 &#xff08;1&#xff09;把时间戳转换为元组形式 &#xff08;2&#xff09;元组转换为时间戳输出 &#xff08;3&#xff09;把元组转换为格式化时间 &#xff08;4&#xff09;把时间戳转换为格式化时间…...

XXL-JOB分布式任务调度框架(二)-策略详解

文章目录1.引言2.任务详解2.1.执行器2.2.基础配置3.路由策略(第一个)-案例4.路由策略(最后一个)-案例5.轮询策略-案例6.随机选取7.轮询选取8.一致性hash9.最不经常使用 (LFU)10.最近最久未使用&#xff08;LRU&#xff09;11.故障转移12.忙碌转移13.分片广播任务14.父子任务15.…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...