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

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...