当前位置: 首页 > news >正文

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.length
  • n == matrix[i].length
  • 1 <= 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.搜索二维矩阵||

题目描述&#xff1a; 编写一个高效的算法来搜索 m*n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例1&#xff1a; 输入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,2…...

Anaconda安装及使用教程

前言&#xff1a;鉴于本人曾经学过计算机双学位&#xff0c;近日突然发现电脑上装了Anaconda&#xff0c;然而脑子里对为什么装这个&#xff0c;啥时候装的以及怎么用的都忘记了。因此&#xff0c;想学习了解下这个软件。 1 Anaconda简介 Anaconda&#xff0c;一个开源的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&#xff0c;引用即可&#xff0c;视操作系统的位数&#xff0c;最重要的是减少了Oracle客户端的安装&#xff1b; 2、web.config字串 <appSettings> <add key"hrp" value"Data Source (…...

分享88个工作总结PPT,总有一款适合您

分享88个工作总结PPT&#xff0c;总有一款适合您 88个工作总结PPT下载链接&#xff1a;https://pan.baidu.com/s/1y08X9RMdIOCncbs28aMgDw?pwd8888 提取码&#xff1a;8888 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 蓝色水彩风年终总结PPT模板 清新水彩简…...

【华为OD题库-002】最佳植树距离-Java

题目 小明在直线的公路上种树&#xff0c;现在给定可以种树的坑位的数星和位置&#xff0c;以及需要种多少棵树苗&#xff0c;问树苗之间的最小间距是多少时&#xff0c;可以保证种的最均匀&#xff08;两棵树苗之间的最小间距最大) 输入描述 输入三行: 第一行一个整数:坑位的数…...

【python与数据结构】(leetcode算法预备知识)

笔记为自我总结整理的学习笔记&#xff0c;若有错误欢迎指出哟~ python与数据结构 Python 中常见的数据类型数据结构1.数组&#xff08;Array&#xff09;2.链表&#xff08;Linked List&#xff09;3.哈希表&#xff08;Hash Table&#xff09;4.队列&#xff08;Queue&#x…...

前端+Python实现Live2D虚拟直播姬

写在前面 很早就在b站上看到有虚拟主播的方案,之前看到的方案主要分为3种: ①用的unity+live2d②有的用的steam的Vtube Studio这款软件③也有基于galgame的。基于纯前端和python的我好像没找到,在掘金看到一篇文章:juejin.cn/post/720474… ,使用的pixi-live2d-display这…...

华纳云 宝塔怎么配置香港服务器多ip?

宝塔面板是一款开源的服务器管理面板&#xff0c;提供了简单易用的图形化界面&#xff0c;使用户能够轻松管理和配置服务器。通过切换到香港服务器多IP&#xff0c;用户可以拥有更多的IP资源&#xff0c;提供更灵活的网络服务。 配置香港服务器多IP 1.登录宝塔面板 打开浏览器&…...

云计算是什么

一文读懂云计算&#xff1a;发展历程、概念技术与现状分析 - 知乎 “现阶段所说的云计算&#xff0c;已经不单单是一种分布式计算&#xff0c;而是分布式计算、效用计算、负载均衡、并行计算、网络存储、热备份冗杂和虚拟化等计算机技术混合演进并跃升的结果。” 云计算的关键…...

【POI-EXCEL-下拉框】POI导出excel下拉框数据太多导致下拉框不显示BUG修复

RT 最近在线上遇到一个很难受的BUG&#xff0c;我一度以为是我代码逻辑出了问题&#xff0c;用了Arthas定位分析之后&#xff0c;开始坚定了信心&#xff1a;大概率是POI的API有问题&#xff0c;比如写入数据过多。 PS&#xff1a;上图为正常的下拉框。但是&#xff0c;当下拉…...

【ES专题】ElasticSearch 高级查询语法Query DSL实战

目录 前言阅读对象阅读导航前置知识数据准备笔记正文一、ES高级查询Query DSL1.1 基本介绍1.2 简单查询之——match-all&#xff08;匹配所有&#xff09;1.2.1 返回源数据_source1.2.2 返回指定条数size1.2.3 分页查询from&size1.2.4 指定字段排序sort 1.3 简单查询之——…...

陕西某小型水库雨水情测报及大坝安全监测项目案例

项目背景 根据《陕西省小型病险水库除险加固项目管理办法》、《陕西省小型水库雨水情测报和大坝安全监测设施建设与运行管理办法》的要求&#xff0c;为保障水库安全运行&#xff0c;对全省小型病险水库除险加固&#xff0c;建设完善雨水情测报、监测预警、防汛道路、通讯设备、…...

pte rs练习方法 请介绍一下crank请介绍一下sanctuary请介绍一下solitary请介绍一下coarse请介绍一下deception

目录 pte rs练习方法 请介绍一下crank 请介绍一下sanctuary 请介绍一下solitary 请介绍一下coarse 请介绍一下deception pte rs练习方法 请介绍一下crank “Crank”一词可以个指不同的事物&#xff0c;具体含义视上下文而定。在不同的领域&#xff0c;这个词有不同的解…...

NLP之LSTM与BiLSTM

文章目录 代码展示代码解读双向LSTM介绍&#xff08;BiLSTM&#xff09; 代码展示 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中不支持多继承&#xff0c;但是一个类可以实现多个接口 下面是自己反复理了很久才敲出来的&#xff0c;涉及到之前学的很多知识点 如果哪看不懂&#xff0c;真…...

Mac收集的几个终端命令

文章目录 转UTF-8编码格式打tag 包 命令&#xff1a;压缩加密文件显示隐藏文件取消Mac电脑安全模式 转UTF-8编码格式 cd到目录下 iconv -f gbk -t utf-8 gbk.txt > utf8.txt打tag 包 命令&#xff1a; cd到目录下 tar -cvf demo.tar.gz demo a demo压缩加密文件 cd 到文…...

206. 反转链表、Leetcode的Python实现

博客主页&#xff1a;&#x1f3c6;看看是李XX还是李歘歘 &#x1f3c6; &#x1f33a;每天分享一些包括但不限于计算机基础、算法等相关的知识点&#x1f33a; &#x1f497;点关注不迷路&#xff0c;总有一些&#x1f4d6;知识点&#x1f4d6;是你想要的&#x1f497; ⛽️今…...

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大模型属于开源大模型,可以本地部署进行行业微调、…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...