【矩阵】240. 搜索二维矩阵 II【中等】
搜索二维矩阵 II
- 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。
- 该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true
解题思路
- 1、根据矩阵的特性,可以发现右上角的元素具有一个特性:它是该行最大的元素,并且是该列最小的元素。
- 2、我们可以从右上角开始搜索,如果当前元素等于目标值,则返回 true。
- 3、如果当前元素大于目标值,则目标值必定在当前元素的左侧列,因此向左移动一列。
- 4、如果当前元素小于目标值,则目标值必定在当前元素的下方行,因此向下移动一行。
- 5、重复步骤 3 和 4,直到找到目标值或者越界。
Java实现
public class Search2DMatrixII {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}int m = matrix.length;int n = matrix[0].length;int row = 0, col = n - 1; // Start from the top-right corner从右上角开始
// {1, 4, 7, 11, 15},
// {2, 5, 8, 12, 19},
// {3, 6, 9, 16, 22},
// {10, 13, 14, 17, 24},
// {18, 21, 23, 26, 30}while (row < m && col >= 0) {if (matrix[row][col] == target) {return true; // Found the target} else if (matrix[row][col] > target) {col--; // Move left in the current row 在当前行向左移动} else {row++; // Move down to the next row 向下移动到下一行}}return false; // Target not found}public static void main(String[] args) {Search2DMatrixII search = new Search2DMatrixII();int[][] matrix = {{1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};int target1 = 5;int target2 = 20;System.out.println("Target 5 found: " + search.searchMatrix(matrix, target1));System.out.println("Target 20 found: " + search.searchMatrix(matrix, target2));}
}
时间空间复杂度
- 时间复杂度:O(m + n),其中 m 和 n 分别是矩阵的行数和列数
- 空间复杂度:O(1),只需要使用常数级别的额外空间
相关文章:
【矩阵】240. 搜索二维矩阵 II【中等】
搜索二维矩阵 II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例 1: 输入:matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22…...
详解uniapp的生命周期
这篇文章主要介绍了 uniapp 的生命周期, 应用生命周期是指应用程序从启动到关闭的整个过程,包括应用程序的启动、前后台切换、退出等, 需要的朋友可以参考下 Uniapp 作为一款跨平台应用开发框架,具有丰富的生命周期,以下是 Uniapp 的生命周期…...
鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:PluginComponent)
提供外部应用组件嵌入式显示功能,即外部应用提供的UI可在本应用内显示。 说明: 该组件从API Version 9开始支持。后续版本如有新增内容,则采用上角标单独标记该内容的起始版本。本组件为系统接口。 子组件 无 接口 PluginComponent(value:…...
mysql笔记:15. 事务和锁
文章目录 一、事务概述二、事务基本操作三、事务保存点四、事务的隔离级别1. READ UNCOMMITTED设置事务的隔离级别 2. READ COMMITTED3. REPEATABLE READ4. SERIALIZABLE 五、MySQL的锁InnoDB的锁类型1. InnoDB的行级锁2. InnoDB的表级锁 死锁 在开发过程中,我们经常…...
Learn OpenGL 15 面剔除
面剔除 尝试在脑子中想象一个3D立方体,数数你从任意方向最多能同时看到几个面。如果你的想象力不是过于丰富了,你应该能得出最大的面数是3。你可以从任意位置和任意方向看向这个球体,但你永远不能看到3个以上的面。所以我们为什么要浪费时间…...
EndeavourOs(arch系)安装sunpinyin输入法(ibus) + 迅雷(xunlei-bin)
输入法 yay -S ibus yay -S ibus-libpinyin yay -S ibus-sunpinyin yay -Q ibus ibus-libpinyin ibus-sunpinyin #验证 # 注销然后打开ibus config... # 在Input Method 添加Chinese->SunPinYin # 使用Ctrl Space, 默认Super Space, 请自行修改 # 再次注销,开…...
Spring Cache框架的介绍和使用
Spring Cache spring cache是一个框架,实现类基于注解的缓存功能,只需要简单的加一个注解,就能实现缓存功能,大大简化我们在业务中操作缓存的代码。 spring cache只是提供了一层抽象,底层可以切换不同的cache实现&am…...
perl 用 XML::Parser 解析 XML文件,访问哈希
本篇我们会看到 Perl 成为知名编程语言的关键特色--哈希 hash(2000年以前叫:关联数组)。 在Perl 中,可以使用各种模块和函数来解析 XML元素和属性。其中,最古老的模块是 XML::Parser,它提供了一组完整的X…...
MATLAB中的矩阵和数组,它们之间有什么区别?
MATLAB中的矩阵和数组:概念、区别与联系 MATLAB(Matrix Laboratory,矩阵实验室)作为一款强大的数学软件,广泛应用于工程、科学、数学、计算机科学等领域。在MATLAB中,矩阵和数组是两个核心概念,…...
python爬虫实战——抖音
目录 1、分析主页作品列表标签结构 2、进入作品页前 判断作品是视频作品还是图文作品 3、进入视频作品页面,获取视频 4、进入图文作品页面,获取图片 5、完整参考代码 6、获取全部作品的一种方法 本文主要使用 selenium.webdriver(Firef…...
Day1-力扣刷题学习打卡
1、两数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以…...
C语言的位操作与位字段
C语言中的位操作允许程序员直接在整型变量的单个位或位组上进行操作。这种操作在许多低级编程任务中非常有用,尤其是在嵌入式系统编程中,如硬件操作、设备驱动及性能优化等场景。位操作主要使用以下几种位操作符: & (按位与&a…...
应用实战|从头开始开发记账本1:如何获取BaaS服务
本期视频开始,我们将通过一系列教程,来详细讲解MemFire Cloud BaaS服务的使用方法,通过这一系列的教程,你将学会如何只使用前端技术完成一个生产级应用的开发和上线。 以下是本期视频主要章节: BaaS服务介绍用户如何…...
el-form v-for循环列表的表单如何校验
1、普通的表单校验直接在最外层<el-form> :model"数据" :rules"规则" ,再在<el-form-item>层设置prop值与model里数据定义的key保持一致即可。 <el-form-item label"名称" prop"ruleName" :rules"[{r…...
笔记:《NCT全国青少年编程能力等级测试教程Python语言编程三级》
NCT全国青少年编程能力等级测试教程Python语言编程三级 ISBN:9787302574859 绪论 专题1 序列和元组 考查方向 考点清单 考点1 组合数据类型 序列类型(字符串、列表、元组);集合类型;映射类型。 考点2 元组类型 (一)元组类型…...
地平线旭日x3派部署yolov5--全流程
地平线旭日x3派部署yolov5--全流程 前言一、深度学习环境安装二、安装docker三、部署3.1、安装工具链镜像3.2、配置天工开物OpenExplorer工具包3.3、创建深度学习虚拟空间,安装依赖:3.4、下载yolov5项目源码并运行3.5、pytorch的pt模型文件转onnx3.6、最…...
【Golang星辰图】Go语言云计算SDK全攻略:深入Go云存储SDK实践
Go语言云计算和存储SDK全面指南 前言 在当今数字化时代,云计算和存储服务扮演着至关重要的角色,为应用程序提供高效、可靠的基础设施支持。本文将介绍几种流行的Go语言SDK,帮助开发者与AWS、Google Cloud、Azure、MinIO、 阿里云和腾讯云等…...
深入理解TCP:序列号、确认号和自动ACK的艺术
深入理解TCP:序列号、确认号和自动ACK的艺术 在计算机网络的世界里,TCP(传输控制协议)扮演着至关重要的角色。它确保了数据在不可靠的网络环境中可靠地、按顺序地传输。TCP的设计充满智慧,其中序列号(Seq&a…...
家电工厂5G智能制造数字孪生可视化平台,推进家电工业数字化转型
家电5G智能制造工厂数字孪生可视化平台,推进家电工业数字化转型。随着科技的飞速发展,家电行业正迎来一场前所未有的数字化转型。在这场制造业数字化转型中,家电5G智能制造工厂数字孪生可视化平台扮演着至关重要的角色。本文将从数字孪生技术…...
ctf_show笔记篇(web入门---代码审计)
301:多种方式进入 从index.php页面来看 只需要访问index.php时session[login]不为空就能访问 那么就在访问index.php的时候上传login 随机一个东西就能进去从checklogin页面来看sql注入没有任何过滤 直接联合绕过 密码随意 还有多种方式可以自己去看代码分析 30…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
深入理解 C++ 左值右值、std::move 与函数重载中的参数传递
在 C 编程中,左值和右值的概念以及std::move的使用,常常让开发者感到困惑。特别是在函数重载场景下,如何合理利用这些特性来优化代码性能、确保语义正确,更是一个值得深入探讨的话题。 在开始之前,先提出几个问题&…...
