力扣第 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…...
JavaScript实用工具lodash库
Lodash中文文档: Lodash 简介 | Lodash中文文档 | Lodash中文网 Lodash是一个功能强大、易于使用的JavaScript实用工具库，它提供了丰富的函数和工具，能够方便地处理集合、字符串、数值、函数等多种数据类型。通过使用Lodash，开发者可以大幅…...
MySQL之JDBC
我们在学习完了数据库的基本操作后，希望和我们的Java程序建立连接，那么我们今天就来一探究竟JDBC是如何让Java程序与数据库建立连接的 1. 什么是JDBC JDBC（Java Data Base Connectivity, Java数据库连接） 是Java程序和数据库之间…...
家校通小程序实战教程04教师管理
目录 1 创建数据源2 搭建管理后台3 搭建查询条件4 功能测试总结 我们上一篇介绍了如何将学生加入班级，学生加入之后就需要教师加入了。教师分为任课老师和班主任，班主任相当于一个班级的管理员，日常可以发布各种任务，发布接龙&…...
vitess使用记录：vtctldclient，设置分表规则
继续探索未完成的事情。 vitess使用记录系列已经写了好几篇了，记录了在测试过程中遇到的各种问题。《vitess使用：从部署到go客户端连接查询》、《vitess使用记录：vtctldclient》、《vitess使用：基于源码运行vtctldclient工具》整…...
Windows利用conda安装gpu版本Faiss + Ubuntu源码安装Faiss-gpu 记录（待更新~）
前言 由于在cpu上使用对向量检索算法时，发现面对数据量较大时，批量匹配耗时会显著增加，影响业务整体响应。便尝试使用GPU来实现检索计算，限于本人技术有限，写不出好算法。便取巧利用Faiss-gpu来检索(* ^ ▽ ^ *) 以下…...
react学习记录
目录结构react优秀代码之react目录结构简洁之道React 作为一个库，不会决定你如何组织项目的结构。这是件好事，因为这样 - 掘金【React】项目的目录结构全面指南_react项目结构-CSDN博客 生命周期【React 面经】生命周期详解：不同阶段与方法解…...
MaskRCNN训练自己的数据集
一. 数据标注 1. 安装labelme软件 conda install labelme2. 运行labelme # 命令行中直接输入 labelme3. 标注 二、训练数据处理 1. 在根目录下创建datasets/demo1文件夹，创建如下几个文件夹 2. 将标注好的.json文件放在json文件夹中 3. 原图放在pic文件夹中 4. …...
metawrap bin_refinement输入checkm数据库地址
这是运行metawrap bin_refinement -o bin_refinement -t 30 -A binning/metabat2_bins/ -B binning/maxbin2_bins/ -C binning/concoct_bins/ -c 50 -x 10 时遇到的报错（在命令行跑的时候遇到的） 参考metaGEM使用小记(解决各种问题)2024 2（三…...
Spring Web MVC其他扩展（详解下）
文章目录 Spring MVC其他扩展（下）异常处理异常处理机制声明式异常好处基于注解异常声明异常处理 拦截器拦截器概念拦截器使用拦截器作用位置图解拦截器案例拦截器工作原理源码 参数校验校验概述操作演示SpringMVC自定义参数验证ValueObject(VO) 文件上传…...
深度学习之 SegNet
可训练的图像分割引擎，包含一个encoder网络，一个对应的decoder网络，衔接像素级分类层，解码网络与VGG16的13层卷积层相同。解码网络是将低分辨率的编码特征图映射到全分辨率的特征图。解码网络使用最大池化层的池化索引进行非线性上…...
Taro React小程序开发框架 总结
目录 一、安装 二、目录结构 三、创建一个自定义页面 四、路由 1、API 2、传参 3、获取路由参数 4、设置TabBar 五、组件 六、API Taro非常好用的小程序框架，React开发者无缝衔接上。 一、安装 官方文档：Taro 文档 注意，项目创建…...
《Django 5 By Example》阅读笔记：p339-p358
《Django 5 By Example》学习第12天，p339-p358总结，总计20页。 一、技术总结 1.项目(购物网站) django-admin startproject myshop 虽然这里只是示例，但我觉得这种命名为 myxxx 的习惯非常不好，因为在实际应用中，是…...
CSS：Web美学的革新之旅
自HTML的诞生之日起，Web页面设计便踏上了一段不断进化的旅程。起初，HTML作为构建网页的骨架，仅承载着最基本的文本结构与少量显示属性。然而，随着互联网的蓬勃发展和用户对视觉体验需求的日益增长，HTML开始不堪重负&am…...
之续集)
java全栈day10--后端Web基础(基础知识)之续集
一、Servlet执行流程 二、Http协议（相对Tomcat和servlet重要一点） 2.1Http-概叙 2.2Http-请求协议 2.2.3请求数据格式 2.2.3请求数据获取 先启动服务器 访问/hello Servlet 访问浏览器端Http协议数据 查看数据...
MySQL 与 MongoDB 存储差异分析
MySQL 与 MongoDB 存储差异分析：为什么随机生成数据的存储空间不同？ 在实际应用中，我们常常需要选择合适的数据库系统来处理不同类型的数据。在这个过程中，数据库的 存储机制 和 性能优化 起着至关重要的作用。对于很多开发者来说…...
【ArcGIS Pro实操第10期】统计某个shp文件中不同区域内的站点数
统计某个shp文件中不同区域内的站点数 方法 1：使用“空间连接 (Spatial Join)”工具方法 2：使用“点计数 (Point Count)”工具方法 3：通过“选择 (Select by Location)”统计方法 4：通过“Python 脚本 (ArcPy)”实现参考 在 ArcGI…...
Django-Vue3-Admin - 现代化的前后端分离权限管理系统
项目介绍 Django-Vue3-Admin是一个基于RBAC（Role-Based Access Control）模型的综合性基础开发平台，专注于权限控制，支持列级别的细粒度权限管理。该项目采用前后端分离架构，技术栈包括: 后端: Django Django REST …...
【Java基础入门篇】二、控制语句和递归算法
Java基础入门篇 二、控制语句和递归算法 2.1 switch-case多分支选择语句 switch执行case语句块时，若没有遇到break，则运行下一个case直到遇到break，最后的default表示当没有case与之匹配时，默认执行的内容，代码示例如…...
PS的功能学习
背景差色较大，就魔棒 魔棒的连续就是倒水点的跨越问题 魔棒的容差的选择就有点看经验了，看颜色的统一程度选择 Ctrl D 取消当前所有的选区 至于快速选择工具，和对象选择工具也差不多，只不过控制范围变成了一块一块的&#x…...
yolov8的深度学习环境安装(cuda12.4、ubuntu22.04）
目录 一、先安装基础环境包 1.首先给Ubuntu安装Chrome浏览器（搜索引擎换成百度即可） 2、ubuntu 22.04中文输入法安装 3、安装 terminator 4、安装WPS for Linux 5、安装其它之前需要先安装anaconda 6、安装配置anaconda 7、安装完成anaconda后创建…...
《JavaEat：探索 Java 在美食世界的奇妙之旅》
在当今数字化的时代，编程语言的应用领域不断拓展，而 Java 作为一种广泛使用且功能强大的编程语言，其影响力早已超越了传统的软件开发范畴。当我们将目光聚焦在美食领域时，会惊喜地发现 Java 也能在其中发挥独特而重要的作用。本文…...
将excel文件中的信息读取后批量生成word文件
在日常办公过程中，可能需要把excel文件中的信息批量生成成百上千份word文档，便于打印、发邮件或存档等，比如根据excel中的合格人员招聘信息生成word合同文件，或是根据excel中的参会人员名单生成word参会通知等。 首先需要制作wor…...
Android 图形系统之三：SurfaceControl
在 Android 系统中，SurfaceControl 是一个关键的类，用于管理应用窗口和屏幕上的显示内容。它与 SurfaceFlinger 紧密交互，通过 BufferQueue 提供高效的图形缓冲区管理能力。SurfaceControl 是 Android 的显示架构中不可或缺的部分，…...
Nodemailer使用教程：在Node.js中发送电子邮件
目录 1. 简介 2. 安装 3. 基本配置 3.1 创建传输器 3.2 配置说明 4. 发送邮件 4.1 基本发送示例 4.2 发送验证码示例 5. 常见问题解决 5.1 "Greeting never received" 错误 5.2 安全建议 SMTP与邮件加密协议详解 1. SMTP简介 1.1 基本特点 2. 加密协…...
shell第二次作业
1. 使用case实现成绩优良差的判断 read -p "请输入你的成绩：" score if ! [[ "$score" ~ ^[0-9]$ ]];then echo "请输入数字" exit 1 fi if [ "$score" -lt 0 ] || [ "$score" -gt 100 ];then echo …...
MySQL Linux 离线安装
下载 进入官网，下载对应的需要MySQL版本，这里是历史版本。 官网 选择第一个MySQL Community Sever社区版，因为这个是免费的。 选择需要的对应版本： 安装 1.将下载好的安装包上传到服务器端 使用FinalShell 客户端连接服务器 …...
万字长文解读深度学习——多模态模型BLIP2
🌺历史文章列表🌺 深度学习——优化算法、激活函数、归一化、正则化 深度学习——权重初始化、评估指标、梯度消失和梯度爆炸 深度学习——前向传播与反向传播、神经网络（前馈神经网络与反馈神经网络）、常见算法概要汇总 万字长…...
postman使用正则表达式提取数据实战篇！
之前篇章中postman多接口关联使用的是通过JSON提取器的方式进行提取。 除了JSON提取器提取数据外还可通过另一种方式——正则表达式来提取数据。 1、使用正则表达式提取器实现接口关联，match匹配 正则匹配表达式将需要提取的字段key:value都放入表达式中ÿ…...
Docker for Everyone Plus——Unbreakable!
修改一下telnet的端口配置，访问第二小问，sudo -l命令允许提权执行的命令： 发现多了这两个限制--security-optno-new-privileges，表明docker run命令必须带上--security-optno-new-privileges参数，这可以防止通过suid机…...
龙迅#LT6912适用于HDMI2.0转HDMI+LVDS/MIPI,分辨率高达4K60HZ,支持音频和HDCP2.2
1. 描述 LT6912是一款高性能的HDMI2.0转HDMI和LVDS和MIPI转换器。 HDMI2.0 输入和输出均支持高达 6Gbps 的数据速率，为4k60Hz视频提供足够的带宽。此外，还支持 HDCP2.2 进行数据解密（无数据 加密）。 对于 LVDS 输出，…...
Linux自动化部署方法（Linux Automated Deployment Method）
💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。 本人主要分享计算机核心技…...
Jmeter测试工具的安装和使用，mac版本，jmeter版本5.2.1
Jmeter测试工具的安装和使用JSON格式请求 一、安装1、安装jdk包和设置java环境2、去官网下载Jmeter3、解压后，打开mac终端，进入apache-jmeter的bin文件开启jmeter 二、使用jmeter1、添加线程2、添加HTTP请求3、配置请求的协议、IP地址、端口号、请求方法…...
)
2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest（cf）（个人记录)
A: 思路：一开始有点懵逼，理解错题意了}， 由于是顺序分配，因此前面的人可以选择的条件更多，后面的人更少，我们从后向前遍历即可 #include<bits/stdc.h>using namespace std;typedef long long ll; ty…...
009 STM32 HAL库介绍
STM32 HAL库（Hardware Abstraction Layer）是STMicroelectronics为STM32系列微控制器提供的一套硬件抽象层库，它旨在简化STM32的开发过程，提高代码的可移植性和可维护性。HAL库通过提供一组统一的API接口，使得开发者无需…...
Java的常识
程序员分类 初级程序员（大学毕业一年以内）大概月薪：2-5K 初中级程序员（工作经验2-3年）大概月薪：6-10K 中级程序员（工作经验4-5年）大概月薪：10-15K 高级程序员（工作经验5++）大概月薪：15K++ 普通公司对于程序员的月薪资天花板25K 工作实景 微信小程序、手机APP、写…...
FreeRTOS——列表及列表项
目录 一、概念及其应用 1.1列表List_t 1.2列表项ListItem_t 1.3迷你列表项MiniListItem_t 二、相关API 三、实现原理 3.1列表初始化 3.2列表项初始化 3.3插入列表项 3.4尾插列表项 3.5列表项的删除 3.6列表的遍历 一、概念及其应用 作为多任务的核心，列…...
ChatGPT 网络安全秘籍（三）
第五章：安全意识和培训 在这一章中，我们将深入探讨网络安全培训和教育的迷人领域，强调了 OpenAI 的大型语言模型（LLMs）在增强和丰富这一关键过程中可以发挥的重要作用。我们将踏上一段旅程，发现 ChatGPT 如…...
深度学习与知识图谱嵌入的结合：从理论到实践
知识图谱嵌入方法主要包括两大类： 方法类型描述矩阵分解类方法基于传统矩阵分解思想，将知识图谱的三元组表示为多个矩阵，并通过分解获得低维向量表示。神经网络方法结合深度学习技术，通过神经网络自动学习知识图谱中实体和关系的…...
Java集成Sa-Token进行认证与授权
引言 软件开发过程中都必须要有的一个功能，那就是认证与授权，经过大佬们的不断更新迭代，使得如今实现认证与授权功能变得相对简单，也许你并不能真正的接触到认证与授权这一功能，除非你接触的项目是从0到1的，…...
【附录】Rust国内镜像设置
目录 前言 （1）设置环境变量 （2）安装Rust （3）设置crates镜像 前言 本节课来介绍下如何在国内高速下载安装Rust和Rust依赖，由于网络原因，我们在安装Rust和下载项目依赖时都很慢&am…...
Rust编程语言代码详细运行、编译方法
以下是针对不同类型的 Rust 代码（以常见的命令行程序为例）详细的运行方法： 前提条件 在运行 Rust 代码之前，确保你已经在系统上安装了 Rust 编程语言环境。如果尚未安装，可以通过以下步骤进行安装： 访问…...
Unity ShaderLab 实现交互地毯
实现思路： 将一个位置坐标值传入到shader的顶点着色器中，和这个值位置相同的顶点沿着法线的y轴方向偏移，然后计算这个值与顶点的距离，在这个范围内的顶点，和凸起的点的位置做插值操作。 Shader Graph实现如下&#x…...
Scala模式匹配——高阶用法
（一）scala的模式匹配 （1）常量 （2）变量 （3）构造器 （4）序列 （5）元组 （6）类型 （7）…...
【简单好抄保姆级教学】javascript调用本地exe程序（谷歌，edge，百度，主流浏览器都可以使用....）
javascript调用本地exe程序 详细操作步骤结果 详细操作步骤 在本地创建一个txt文件依次输入 1.指明所使用注册表编程器版本 Windows Registry Editor Version 5.00这是脚本的第一行，指明了所使用的注册表编辑器版本。这是必需的，以确保脚本能够被正确解…...
C#热更原理与HybridCLR
一、Mono的诞生 在Mono之前，C#虽然很好，但是只在windows家族平台上使用，就这点C#与Java就无法比。于是微软公司向ECMA申请将C#作为一种标准。在2001年12月，ECMA发布了ECMA-334 C#语言规范。C#在2003年成为一个ISO标准（ISO/IEC 23270）。意味着只要你遵守CLI（Common Lang…...
arcgis for js点击聚合要素查询其包含的所有要素
功能说明 上一篇讲了实现聚合效果, 但是点击聚合效果无法获取到该聚合点包含的所有点信息 这一篇是对如何实现该功能的案例 实现 各属性说明需要自行去官网查阅 官网案例 聚合API 没空说废话了, 加班到12点,得休息了, 直接运行代码看效果就行, 相关重点和注意事项都在代码注…...
k8s Init:ImagePullBackOff 的解决方法
kubectl describe po (pod名字) -n kube-system 可查看pod所在的节点信息 例如： kubectl describe po calico-node-2lcxx -n kube-system 执行拉取前先把用到的节点的源换了 sudo mkdir -p /etc/docker sudo tee /etc/docker/daemon.json <<-EOF {"re…...
HASH256开源代码计算错误问题
计算量超500KB报错 OTA升级中可能会涉及到CRC、hash校验等算法，小编从网上抄到了HASH256的源码，拿来使用的时候却发现了一个问题，当源文件约大于500KB的时候会发现其计算出的hash值出现错误。 经过实际测试得知，当源文件大于约50…...
对象流—ObjectInputStream 和 ObjectOutputStream
对象流(ObjectInputStream和ObjectOutputStream)是Java中用于读写对象的流，可以将对象直接写入到流中，或者从流中读取对象。 ObjectOutputStream将对象序列化为字节流，可以将对象写入文件或网络流中。ObjectInputStream则将字节流反序列化为…...