当前位置: 首页 > 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.…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...