搜索二维矩阵[中等]

news/2024/2/24 7:39:09/文章来源:https://blog.csdn.net/zhengzhaoyang122/article/details/136097777

一、题目

给你一个满足下述两条属性的m x n整数矩阵:
【1】每行中的整数从左到右按非严格递增顺序排列。
【2】每行的第一个整数大于前一行的最后一个整数。

给你一个整数target,如果target在矩阵中,返回true;否则,返回false

示例 1:

输入: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出: true

示例 2:

输入: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出: false

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

二、代码

【1】两次二分查找: 由于每行的第一个元素大于前一行的最后一个元素,且每行元素是升序的,所以每行的第一个元素大于前一行的第一个元素,因此矩阵第一列的元素是升序的。

我们可以对矩阵的第一列的元素二分查找,找到最后一个不大于目标值的元素,然后在该元素所在行中二分查找目标值是否存在。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}

时间复杂度: O(log ⁡m+log ⁡n)=O(log ⁡mn),其中mn分别是矩阵的行数和列数。
空间复杂度: O(1)

【2】一次二分查找: 若将矩阵每一行拼接在上一行的末尾,则会得到一个升序数组,我们可以在该数组上二分找到目标元素。代码实现时,可以二分升序数组的下标,将其映射到原矩阵的行和列上。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}

时间复杂度: O(log⁡mn),其中mn分别是矩阵的行数和列数。
空间复杂度: O(1)

两种方法殊途同归,都利用了二分查找,在二维矩阵上寻找目标值。值得注意的是,若二维数组中的一维数组的元素个数不一,方法二将会失效,而方法一则能正确处理。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_963348.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux技术宝典】Linux入门:揭开Linux的神秘面纱

文章目录 官网Linux 环境的搭建方式一、什么是Linux&#xff1f;二、Linux的起源与发展三、Linux的核心组件四、Linux企业应用现状五、Linux的发行版本六、为什么选择Linux&#xff1f;七、总结 Linux&#xff0c;一个在全球范围内广泛应用的开源操作系统&#xff0c;近年来越来…

树莓派编程基础与硬件控制

1.编程语言 Python 是一种泛用型的编程语言&#xff0c;可以用于大量场景的程序开发中。根据基于谷歌搜 索指数的 PYPL&#xff08;程序语言流行指数&#xff09;统计&#xff0c;Python 是 2019 年 2 月全球范围内最为流行 的编程语言 相比传统的 C、Java 等编程语言&#x…

生成树技术华为ICT网络赛道

9.生成树 目录 9.生成树 9.1.生成树技术概述 9.2.STP的基本概念及工作原理 9.3.STP的基础配置 9.4.RSTP对STP的改进 9.5.生成树技术进阶 9.1.生成树技术概述 技术背景&#xff1a;二层交换机网络的冗余性与环路 典型问题1&#xff1a;广播风暴 典型问题2&#xff1a;MA…

《UE5_C++多人TPS完整教程》学习笔记10 ——《P11 设置加入游戏会话(Setup for Joining Sessions)》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P11 设置加入游戏会话&#xff08;Setup for Joining Sessions&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&…

Linux开发:PAM1 介绍

PAM(Pluggable Authentication Modules )是Linux提供的一种通用的认证方式,他可以根据需要动态的加载认证模块,从而减少认证开发的工作量以及提供认证的灵活度。 1.PAM的框架 PAM的框架由一下几个部分构成 1)应用程序,即需要使用认证服务的程序,这些应用程序是使用抽象…

单例模式 C++

6 种 单例 的手写&#xff0c;都是懒汉&#xff08;饿汉代码在 “懒汉 / 饿汉的区别”&#xff09; 目录 ✊前言 &#x1f33c;GPT解析 &#x1f33c;概念解析 RAII 懒汉 / 饿汉的区别 特点 举例 单例 -- 伪代码 适用场景 单例 -- 实现方式 优缺点 &#x1f382;手…

【Iceberg学习二】Branch和Tag在Iceberg中的应用

Iceberg 表元数据保持一个快照日志&#xff0c;记录了对表所做的更改。快照在 Iceberg 中至关重要&#xff0c;因为它们是读者隔离和时间旅行查询的基础。为了控制元数据大小和存储成本&#xff0c;Iceberg 提供了快照生命周期管理程序&#xff0c;如 expire_snapshots&#xf…

《Linux 简易速速上手小册》第9章: 备份与恢复策略(2024 最新版)

文章目录 9.1 理解备份的重要性9.1.1 重点基础知识9.1.2 重点案例&#xff1a;数据中心遭受火灾9.1.3 拓展案例&#xff1a;个人电脑硬盘故障9.1.4 企业级数据库被恶意软件加密 9.2 实施备份策略9.2.1 重点基础知识9.2.2 重点案例&#xff1a;为中小企业实施备份策略9.2.3 拓展…

springboot165科研工作量管理系统的设计与实现

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…

基于SpringBoot+Vue的服装销售商城系统

末尾获取源码作者介绍&#xff1a;大家好&#xff0c;我是墨韵&#xff0c;本人4年开发经验&#xff0c;专注定制项目开发 更多项目&#xff1a;CSDN主页YAML墨韵 学如逆水行舟&#xff0c;不进则退。学习如赶路&#xff0c;不能慢一步。 目录 一、项目简介 二、开发技术与环…

bert-vits2本地部署报错疑难问题汇总

环境&#xff1a; bert-vits2.3 win 和wsl 问题描述&#xff1a; bert-vits2本地部署报错疑难问题汇总 解决方案&#xff1a; 问题1: Conda安装requirements里面依赖出现ERROR: No matching distribution found for opencc1.1.6 解决方法 需要在 Python 3.11 上使用 Op…

linux服务器如何提高游戏帧率?

在Linux服务器上&#xff0c;由于硬件配置和系统的限制&#xff0c;提高游戏帧率变得更加困难。但是通过一些优化和调整&#xff0c;我们仍然可以提升Linux服务器上的游戏性能。 首先我们需要了解游戏帧率与服务器性能之间的关系。游戏帧率是指游戏每秒渲染的帧数&#xff0c;…

《统计学简易速速上手小册》第6章:多变量数据分析(2024 最新版)

文章目录 6.1 主成分分析&#xff08;PCA&#xff09;6.1.1 基础知识6.1.2 主要案例&#xff1a;客户细分6.1.3 拓展案例 1&#xff1a;面部识别6.1.4 拓展案例 2&#xff1a;基因数据分析 6.2 聚类分析6.2.1 基础知识6.2.2 主要案例&#xff1a;市场细分6.2.3 拓展案例 1&…

【XR806开发板试用】轻松连上华为云实现物联网

本文为极术社区XR806试用活动文章。 一.开始 偶然的机会在网上看到了鸿蒙开发板的试用,作为一个"老鸿蒙"岂能放弃这个机会,报名之后不出意料地得到了使用名额,在此感谢极术社区. 收到开发板之后其实还有点失望了,就那么一个小小的核心板,其他啥也没有,连一根数据线…

【精选】java进阶——包和final

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【python】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收藏…

【CC++】内存管理2:new + delete

前言 今天继续来学new和delete operator new 与operator delete函数 new和delete是用户进行动态内存申请和释放的操作符&#xff0c;operator new 和operator delete是系统提供的全局函数&#xff0c;new在底层调用operator new全局函数来申请空间&#xff0c;delete在底层通…

Android Studio无法安装Git问题解决(折中方案)

安装配置好studio&#xff0c;往往会使用git克隆github上面的项目&#xff0c;但是却发现git无法正确安装&#xff0c;本文将介绍如何解决git无法安装这一问题。 对于git安装&#xff0c;实际比较复杂&#xff0c;可以参考这一篇博客。 Git 详细安装教程&#xff08;详解 Gi…

13 年后,我如何用 Go 编写 HTTP 服务(译)

原文&#xff1a;Mat Ryer - 2024.02.09 大约六年前&#xff0c;我写了一篇博客文章&#xff0c;概述了我是如何用 Go 编写 HTTP 服务的&#xff0c;现在我再次告诉你&#xff0c;我是如何写 HTTP 服务的。 那篇原始的文章引发了一些热烈的讨论&#xff0c;这些讨论影响了我今…

JS高级(四)- 深浅拷贝、异常处理、处理this、防抖节流md

文章目录 1.深浅拷贝1.1浅拷贝1.2深拷贝1.2.1递归实现深拷贝1.2.2 js库lodash里面cloneDeep内部实现了深拷贝1.2.3 JSON序列化 2.异常处理2.1 throw2.2 try ... catch2.3 debugger 3.处理this(this小结)3.1普通函数3.2箭头函数3.3改变this指向3.3.1 call3.3.2 apply3.3.3 bind3…

rediss集群 三主三从集群模式

三主三从集群模式 1)、新建redis集群目录&#xff1a;7001~7006工作目录【/app/soft/redis-cluster/目下】 2&#xff09;、在7001~7006 目录下创建bin和conf 目录&#xff0c;然后将/app/soft/redis/bin目录下的文件分别拷贝到7001~7006 目录&#xff0c;然后在7001~7006 目…