力扣第 74 题是 搜索二维矩阵
题目描述
给定一个 m x n 的矩阵 matrix 和一个目标值 target,请你编写一个函数来判断目标值 target 是否在矩阵中。
- 每行的元素按升序排列。
- 每列的元素按升序排列。
示例 1
输入:
matrix = [[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14, 17]
]
target = 5
输出:
true
示例 2
输入:
matrix = [[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14, 17]
]
target = 20
输出:
false
解题思路
1. 暴力法
最简单的做法是遍历整个矩阵,逐个元素进行比较,看是否等于 target。这种方法的时间复杂度是 O(m * n),其中 m 是矩阵的行数,n 是矩阵的列数。
2. 优化方法(从矩阵的角落开始)
考虑到矩阵的特点:每行和每列都是升序排列的,我们可以利用这一点来提高搜索效率。
一种常见的优化方法是从矩阵的右上角或者左下角开始搜索。这里我们选择从右上角开始:
- 如果目标值等于当前位置的值,直接返回
true。 - 如果目标值小于当前位置的值,则可以排除当前列,因为该列的元素都大于当前位置的值,移动到当前行的左边(即向左移动)。
- 如果目标值大于当前位置的值,则可以排除当前行,因为该行的元素都小于当前位置的值,移动到当前列的下方(即向下移动)。
这种方法的时间复杂度是 O(m + n),比暴力法更高效。
实现代码(右上角开始)
#include <stdio.h>
#include <stdbool.h>bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {int m = matrixSize; // 矩阵的行数int n = *matrixColSize; // 矩阵的列数int row = 0;int col = n - 1; // 从右上角开始while (row < m && col >= 0) {if (matrix[row][col] == target) {return true; // 找到目标值} else if (matrix[row][col] < target) {row++; // 目标大于当前值,向下移动} else {col--; // 目标小于当前值,向左移动}}return false; // 未找到目标值
}int main() {// 示例矩阵int matrix[4][4] = {{1, 4, 7, 11},{2, 5, 8, 12},{3, 6, 9, 16},{10, 13, 14, 17}};int matrixSize = 4;int matrixColSize = 4;int target = 5;// 使用动态数组传递矩阵int* matrixPtr[4];for (int i = 0; i < matrixSize; i++) {matrixPtr[i] = matrix[i];}bool result = searchMatrix(matrixPtr, matrixSize, &matrixColSize, target);if (result) {printf("Found %d in the matrix.\n", target);} else {printf("%d not found in the matrix.\n", target);}return 0;
}
解释
-
矩阵初始化:
- 在
main函数中,我们定义了一个 4x4 的静态二维数组matrix,并将其转换为指针数组matrixPtr,用于传递给searchMatrix函数。
- 在
-
搜索方法:
searchMatrix函数从矩阵的右上角开始搜索,通过比较当前值与目标值的大小来决定向下或向左移动。- 如果目标值等于当前元素,返回
true;如果目标值小于当前元素,向左移动;如果目标值大于当前元素,向下移动。
-
返回值:
- 如果在搜索过程中找到了目标值,返回
true;否则返回false。
- 如果在搜索过程中找到了目标值,返回
时间复杂度和空间复杂度
-
时间复杂度:
- 每次操作后,我们要么向下移动一行,要么向左移动一列。所以,最多需要
m + n次操作,其中m是矩阵的行数,n是矩阵的列数。因此时间复杂度是 O(m + n)。
- 每次操作后,我们要么向下移动一行,要么向左移动一列。所以,最多需要
-
空间复杂度:
- 只使用了常数额外空间,所以空间复杂度是 O(1)。
相关文章:
力扣第 74 题是 搜索二维矩阵
题目描述 给定一个 m x n 的矩阵 matrix 和一个目标值 target,请你编写一个函数来判断目标值 target 是否在矩阵中。 每行的元素按升序排列。每列的元素按升序排列。 示例 1 输入: matrix [[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14…...
[极客大挑战 2019]BabySQL--详细解析
信息搜集 进入界面: 输入用户名为admin,密码随便输一个: 发现是GET传参,有username和password两个传参点。 我们测试一下password点位能不能注入: 单引号闭合报错,根据报错信息,我们可以判断…...
实现Linux平台自定义协议族
一 简介 我们常常在Linux系统中编写socket接收TCP/UDP协议数据,大家有没有想过它怎么实现的,如果我们要实现socket接收自定义的协议数据又该怎么做呢?带着这个疑问,我们一起往下看吧~~ 二 Linux内核函数简介 在Linux系统中要想…...
RL78/G15 Fast Prototyping Board Arduino IDE 平台开发过程
这是一篇基于RL78/G15 Fast Prototyping Board的Arduino IDE开发记录 RL78/G15 Fast Prototyping Board硬件简介(背景)基础测试(方法说明/操作说明)开发环境搭建(方法说明/操作说明代码结果)Arduino IDE RL…...
YOLOv11 NCNN安卓部署
YOLOv11 NCNN安卓部署 前言 yolov11 NCNN安卓部署 目前的帧率可以稳定在20帧左右,下面是这个项目的github地址:https://github.com/gaoxumustwin/ncnn-android-yolov11 上面的检测精度很低时因为这个模型只训练了5个epoch,使用3090训练一个…...
对载入的3dtiles进行旋转、平移和缩放变换。
使用 params: {tx: 129.75845, //模型中心X轴坐标(经度,单位:十进制度)//小左ty: 46.6839, //模型中心Y轴坐标(纬度,单位:十进制度)//小下tz: 28, //模型中心Z轴坐标(高…...
Rust个人认为将抢占C和C++市场,逐渐成为主流的开发语言
本人使用C开发8年、C#开发15年、中间使用JAVA开发过项目、后期在学习过程中发现了Rust语言说它是最安全的语言,能够解决C、C的痛点、于是抽出一部分时间网上买书,看网上资料进行学习,这一学习起来发现和其它语言比较起来,在编码的…...
在openEuler中使用top命令
在openEuler中使用top命令 概述 top 命令是Linux系统中最常用的实时性能监控工具之一,允许用户查看系统的整体状态,包括CPU使用率、内存使用情况、运行中的进程等。本文档将详细介绍如何在openEuler操作系统中有效利用top命令进行系统监控。 启动top命令 打开终端并输入t…...
探索文件系统,Python os库是你的瑞士军刀
文章目录 探索文件系统,Python os库是你的瑞士军刀第一部分:背景介绍第二部分:os库是什么?第三部分:如何安装os库?第四部分:简单库函数使用方法1. 获取当前工作目录2. 改变当前工作目录3. 列出目…...
【小白学机器学习41】如何从正态分布的总体中去抽样? 获得指定正态分布的样本的2种方法
目录 1 目标:使用2种方法,去从正态分布的总体中去抽样,获得样本 1.1 step1: 首先,逻辑上需要先有符合正态分布的总体population 1.2 从总体中取得样本,模拟抽样的过程 2 从正态分布抽样的方法1 3 从正态分布抽样…...
将VSCode设置成中文语言环境
目录 VSCode默认是英文语言环境,这对于像我这种英语比较菜的人来说不是那么友好 另外也习惯了用中文,所以接下来介绍下如何将VSCode设置成中文语言环境。 1、打开VSCode软件,按快捷键【CtrlShiftP】 2、在弹出的搜索框中输入【configure l…...
Applied Intelligence投稿
一、关于手稿格式: 1、该期刊是一个二区的,模板使用Springer nature格式, 期刊投稿要求,详细期刊投稿指南,大部分按Soringernature模板即可,图片表格声明参考文献命名要求需注意。 2、参考文献ÿ…...
AI-agent矩阵营销:让品牌传播无处不在
矩阵营销是一种通过多平台联动构建品牌影响力的策略,而 AI-agent 技术让这一策略变得更加智能化。AI社媒引流王凭借其矩阵管理功能,帮助品牌在多个平台上实现深度覆盖与精准传播。 1. 矩阵营销的优势 品牌触达更广:多平台联动可以覆盖不同用…...
【0346】Postgres内核 Startup Process 通过 signal 与 postmaster 交互实现 (5)
1. Startup Process 进程 postmaster 初始化过程中, 在进入 ServerLoop() 函数之前,会先通过调用 StartChildProcess() 函数来开启辅助进程,这些进程的目的主要用来完成数据库的 XLOG 相关处理。 如: 核实 pg_wal 和 pg_wal/archive_status 文件是否存在Postgres先前是否发…...
NSSCTF-做题笔记
[羊城杯 2020]easyre 查壳,无壳,64位,ida打开 encode_one encode_tow encode_three 那么我们开始一步一步解密,从最外层开始 def decode_three(encrypted_str):decrypted_str ""for char in encrypted_str:char_code …...
【小白学机器学习35】数据表:整洁数据表,交叉表/列联表,以及两者转化pd.pivot_table()
目录 1 虽然这是个很基础的知识,但是我觉得有必要记录下 2 整洁数据表 3 交叉数据表的2种形式 3.0 交叉表的名字 3.1 2维的交叉表 3.2 用2维表现3维的 3.3 上述内容,具体的markdown文本 4 交叉数据表 4.1 交叉数据表并不整洁 4.2 但是交叉表也…...
springboot旅游管理系统的设计与实现
springboot旅游管理系统的设计与实现 如需源码pc端👉👉👉资源 手机端👉👉👉资源 摘 要 信息化社会内需要与之针对性的信息获取途径,但是途径的扩展基本上为人们所努力的方向,由于…...
k8s 1.28 聚合层部署信息记录
–requestheader-client-ca-file –requestheader-allowed-namesfront-proxy-client –requestheader-extra-headers-prefixX-Remote-Extra- –requestheader-group-headersX-Remote-Group –requestheader-username-headersX-Remote-User –proxy-client-cert-file –proxy-cl…...
自由学习记录(25)
只要有修改,子表就不用元表的参数了,用自己的参数(只不过和元表里的那个同名) 子表用__index“继承”了父表的值,此时子表仍然是空表 一定是创建这样一个同名的变量在原本空空的子表里, 传参要传具体的变…...
关于函数式接口和编程的解析和案例实战
文章目录 匿名内部类“匿名”在哪里 函数式编程lambda表达式的条件Supplier使用示例 ConsumeracceptandThen使用场景 FunctionalBiFunctionalTriFunctional 匿名内部类 匿名内部类的学习和使用是实现lambda表达式和函数式编程的基础。是想一下,我们在使用接口中的方…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
