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

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...