LeetCode热题100 240.搜索二维矩阵||
题目描述:
编写一个高效的算法来搜索 m*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示例 2:
输入: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 = 20 输出:false提示:
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-10^9 <= matrix[i][j] <= 10^9- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9
解题思路:
首先最简单的办法就是暴力法直接遍历数组判断target是否出现,时间复杂度为O(mn),没有利用到这个题目矩阵的特点,显然这不是最优解。
根据矩阵 "每行的所有元素从左到右升序排列,每列的所有元素从上到下升序排列"的特点,容易想到可以利用二分法查找每一行或每一列来判断target是否出现,时间复杂度为O(mlogn)或O(nlogm)。
那么还有没有更好的办法呢?
仔细观察示例1中的矩阵,用红线标出每行可能出现target(5)的位置

标出示例2矩阵可能出现target(20)的位置

可以发现红线把矩阵分隔成了两块区域,左边区域元素都小于target,右边区域元素都大于target,那么不管是左边区域还是右边区域都不可能会出现target,所以只要想办法遍历矩阵红线标记位置,其他位置就不用去遍历。
算法流程:
1.可以选矩阵的一角作为起点,选右上角(0,n-1)为起点开始遍历,元素matrix[i][j]:
- matrix[i][j]小于target,因为每行元素从左到右是升序,左边元素一定比matrix[i][j]小,所以应该往下搜索,i增加1。
- matrix[i][j]等于target返回true。
- matrix[i][j]大于target,因为每列从上到下是升序,下边元素一定比matrix[[i][j]大,所以应该往左搜索,j减少1。
2.若i或j出界,未查找到target,返回false。
以下是算法Java实现:
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m=matrix.length;int n=matrix[0].length;int i=0;int j=n-1;while(i<m&&j>=0){if(matrix[i][j]==target) return true;if(matrix[i][j]>target){j--;} else{i++;}}return false; }
}
以上算法在官方题解中称为"Z字形查找",Z字形查找每次可以排除一行或一列的元素,时间复杂度为O(m+n),空间复杂度为O(1)。
另一种理解方式——二叉搜索树
如下图所示,我们将矩阵逆时针旋转 45° ,并将其转化为图形式,发现其类似于 二叉搜索树 ,即对于每个元素,其左分支元素更小、右分支元素更大。因此,通过从 “根节点” 开始搜索,遇到比 target 大的元素就向左,反之向右,即可找到目标值 target 。

相关文章:
LeetCode热题100 240.搜索二维矩阵||
题目描述: 编写一个高效的算法来搜索 m*n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例1: 输入:matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,2…...
Anaconda安装及使用教程
前言:鉴于本人曾经学过计算机双学位,近日突然发现电脑上装了Anaconda,然而脑子里对为什么装这个,啥时候装的以及怎么用的都忘记了。因此,想学习了解下这个软件。 1 Anaconda简介 Anaconda,一个开源的Pyth…...
动态规划算法实现------转换(编辑、变换)问题
目录 一、字符串转换问题 1.1问题 1.2确定动态规则(DP、状态转移方程)、初始值 (1)插入操作实现状态转移 (2)删除操作实现状态转移 (3)替换操作实现状态转移 (4)初始值 1.3动态规划算法代码实现 (1)完整代码 (2)程序速度优化 二、矩阵变换问题 2.1问题 2.2矩阵乘法 (1)矩阵相乘…...
C#使用Oracle.ManagedDataAccess.dll
1、添加引用 在网上下载一个Oracle.ManagedDataAccess.dll,引用即可,视操作系统的位数,最重要的是减少了Oracle客户端的安装; 2、web.config字串 <appSettings> <add key"hrp" value"Data Source (…...
分享88个工作总结PPT,总有一款适合您
分享88个工作总结PPT,总有一款适合您 88个工作总结PPT下载链接:https://pan.baidu.com/s/1y08X9RMdIOCncbs28aMgDw?pwd8888 提取码:8888 Python采集代码下载链接:采集代码.zip - 蓝奏云 蓝色水彩风年终总结PPT模板 清新水彩简…...
【华为OD题库-002】最佳植树距离-Java
题目 小明在直线的公路上种树,现在给定可以种树的坑位的数星和位置,以及需要种多少棵树苗,问树苗之间的最小间距是多少时,可以保证种的最均匀(两棵树苗之间的最小间距最大) 输入描述 输入三行: 第一行一个整数:坑位的数…...
【python与数据结构】(leetcode算法预备知识)
笔记为自我总结整理的学习笔记,若有错误欢迎指出哟~ python与数据结构 Python 中常见的数据类型数据结构1.数组(Array)2.链表(Linked List)3.哈希表(Hash Table)4.队列(Queue&#x…...
前端+Python实现Live2D虚拟直播姬
写在前面 很早就在b站上看到有虚拟主播的方案,之前看到的方案主要分为3种: ①用的unity+live2d②有的用的steam的Vtube Studio这款软件③也有基于galgame的。基于纯前端和python的我好像没找到,在掘金看到一篇文章:juejin.cn/post/720474… ,使用的pixi-live2d-display这…...
华纳云 宝塔怎么配置香港服务器多ip?
宝塔面板是一款开源的服务器管理面板,提供了简单易用的图形化界面,使用户能够轻松管理和配置服务器。通过切换到香港服务器多IP,用户可以拥有更多的IP资源,提供更灵活的网络服务。 配置香港服务器多IP 1.登录宝塔面板 打开浏览器&…...
云计算是什么
一文读懂云计算:发展历程、概念技术与现状分析 - 知乎 “现阶段所说的云计算,已经不单单是一种分布式计算,而是分布式计算、效用计算、负载均衡、并行计算、网络存储、热备份冗杂和虚拟化等计算机技术混合演进并跃升的结果。” 云计算的关键…...
【POI-EXCEL-下拉框】POI导出excel下拉框数据太多导致下拉框不显示BUG修复
RT 最近在线上遇到一个很难受的BUG,我一度以为是我代码逻辑出了问题,用了Arthas定位分析之后,开始坚定了信心:大概率是POI的API有问题,比如写入数据过多。 PS:上图为正常的下拉框。但是,当下拉…...
【ES专题】ElasticSearch 高级查询语法Query DSL实战
目录 前言阅读对象阅读导航前置知识数据准备笔记正文一、ES高级查询Query DSL1.1 基本介绍1.2 简单查询之——match-all(匹配所有)1.2.1 返回源数据_source1.2.2 返回指定条数size1.2.3 分页查询from&size1.2.4 指定字段排序sort 1.3 简单查询之——…...
陕西某小型水库雨水情测报及大坝安全监测项目案例
项目背景 根据《陕西省小型病险水库除险加固项目管理办法》、《陕西省小型水库雨水情测报和大坝安全监测设施建设与运行管理办法》的要求,为保障水库安全运行,对全省小型病险水库除险加固,建设完善雨水情测报、监测预警、防汛道路、通讯设备、…...
pte rs练习方法 请介绍一下crank请介绍一下sanctuary请介绍一下solitary请介绍一下coarse请介绍一下deception
目录 pte rs练习方法 请介绍一下crank 请介绍一下sanctuary 请介绍一下solitary 请介绍一下coarse 请介绍一下deception pte rs练习方法 请介绍一下crank “Crank”一词可以个指不同的事物,具体含义视上下文而定。在不同的领域,这个词有不同的解…...
NLP之LSTM与BiLSTM
文章目录 代码展示代码解读双向LSTM介绍(BiLSTM) 代码展示 import pandas as pd import tensorflow as tf tf.random.set_seed(1) df pd.read_csv("../data/Clothing Reviews.csv") print(df.info())df[Review Text] df[Review Text].astyp…...
【实现多个接口的使用】
文章目录 前言实现多个接口接口间的继承接口使用实例给对象数组排序创建一个比较器 总结 前言 实现多个接口 Java中不支持多继承,但是一个类可以实现多个接口 下面是自己反复理了很久才敲出来的,涉及到之前学的很多知识点 如果哪看不懂,真…...
Mac收集的几个终端命令
文章目录 转UTF-8编码格式打tag 包 命令:压缩加密文件显示隐藏文件取消Mac电脑安全模式 转UTF-8编码格式 cd到目录下 iconv -f gbk -t utf-8 gbk.txt > utf8.txt打tag 包 命令: cd到目录下 tar -cvf demo.tar.gz demo a demo压缩加密文件 cd 到文…...
206. 反转链表、Leetcode的Python实现
博客主页:🏆看看是李XX还是李歘歘 🏆 🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺 💗点关注不迷路,总有一些📖知识点📖是你想要的💗 ⛽️今…...
VS2022 打包WPF安装程序最新教程(图文详解)
文章目录 前言一、安装打包Installer插件1、单独安装2、VS中在线安装二、使用步骤1、创建安装项目2、安装项目主界面3、添加项目输出4、添加快捷方式图标5、添加卸载项目a、新建项目b、添加项目输出c、创建快捷方式6、给快捷方式添加图标a、在Resource文件夹中添加图标文件b、选…...
清华大模型GLM
2022年,清华大学发布了一款具有重要意义的 GLM 大模型,它不仅在中文语言处理方面取得了显著的进展,还在英文语言处理方面表现出了强大的能力。GLM大模型区别于OpenAI GPT在线大模型只能通过API方式获取在线支持的窘境,GLM大模型属于开源大模型,可以本地部署进行行业微调、…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...


