剑指offer-二维数组中的查找
文章目录
- 题目描述
- 题解一 无脑暴力循环
- 题解二 初始二分法
🌕博客x主页:己不由心王道长🌕!
🌎文章说明:剑指offer-二维数组中的查找🌎
✅系列专栏:剑指offer
🌴本篇内容:对剑指offer中的数组进行学习和解析🌴
☕️每日一语:这个世界本来就不完美,如果我们再不接受不完美的自己,那我们要怎么活。☕️
🚩 交流社区:己不由心王道长(优质编程社区)
题目描述
在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 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。
给定 target = 20,返回 false。
限制:
0 <= n <= 1000
0 <= m <= 1000
题解一 无脑暴力循环
思路:
由于题目给出的是一个n * m 的二维数组,不考虑其他因素,只要判断数组里面有没有目标元素而言,直接双层for循环暴力解决,代码如下:
class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {for(int i=0;i<matrix.length;i++){for(int j= 0;j<matrix[i].length;j++){if(matrix[i][j]==target){return true;}}}return false;}
}
结果:

想法:确实无脑暴力可解,但是这里的执行用时感觉不对劲,两层for循环,时间复杂度O(n*m),应该不算快才对。
题解二 初始二分法
思路:

如图所示,题目给出的是没一行都按照从左到右非递减的顺序排列,就是说其实这个数组在一维的角度来说是有顺序的,当然二维也有,仔细观察就能发现————用处就是,我们的二分法在应用的时候就需要有顺序的数组,明白了吗?
先看代码:
class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {for(int i =0;i<matrix.length;i++){int left=0;//在while循环外侧设置,当while循环结束后可以重新给left和right赋值int right=matrix[0].length-1;//开始是在matrix[0][x]使用二分法,就是每一行使用二分,一行结束之后换到下一行while(left<=right){int middle = left+((right-left)/2);if(matrix[i][middle]==target){return true;}else if(target<matrix[i][middle]){//目标小,向左查找right=middle-1;}else{left = middle+1;}}}return false;}
}
这里在每一行上都使用了二分法,就是在每次for循环,在循环行的时候对行进行二分法。
结果

相关文章:
剑指offer-二维数组中的查找
文章目录题目描述题解一 无脑暴力循环题解二 初始二分法🌕博客x主页:己不由心王道长🌕! 🌎文章说明:剑指offer-二维数组中的查找🌎 ✅系列专栏:剑指offer 🌴本篇内容:对剑…...
怎么设计一个秒杀系统
1、系统部署 秒杀系统部署要单独区别开其他系统单独部署,这个系统的流量肯定很大,单独部署。数据库也要单独用一个部署的数据库或者集群,防止高并发导致整个网站不可用。 2、防止超卖 100个库存,1000个人买,要保证不…...
程序参数解析C/C++库 The Lean Mean C++ Option Parser
开发中我们经常使用程序参数,根据参数的不同来实现不同的功能。POSIX和GNU组织对此都制定了一些标准,为了我们程序更为通用标准,建议遵循这些行业内的规范,本文介绍的开源库The Lean Mean C Option Parser就可以很好满足我们的需求…...
Java中的深拷贝和浅拷贝
目录 🍎引出拷贝 🍎浅拷贝 🍎深拷贝 🍎总结 引出拷贝 现在有一个学生类和书包类,在学生类中有引用类型的书包变量: class SchoolBag {private String brand; //书包的品牌private int size; //书…...
大文件上传
上图就是大致的流程一、标题图片上传课程的标题图片Ajax发送请求到后端后端接收到图片使用IO流去保存图片,返回图片的信息对象JS回调函数接收对象通过$("元素id").val(值),方式给页面form表达img标签src属性值,达到上传图片并回显二…...
Python每日一练(20230327)
目录 1. 最大矩形 🌟🌟🌟 2. 反转链表 II 🌟🌟 3. 单词接龙 II 🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C每日…...
Centos7 升级内核到5.10mellanox 编译安装
升级5.10内核 #uname -r 重启后 进入新的内核 进入新的内核信息 直接查看是看不到gcc版本 5.10需要高版本gcc 才可以进行编译...
冯诺依曼,操作系统以及进程概念
文章目录一.冯诺依曼体系结构二.操作系统(operator system)三.系统调用和库函数四.进程1.进程控制块(PCB)2.查看进程3.系统相关的调用4.fork介绍(并发引入)五.总结一.冯诺依曼体系结构 计算机大体可以说是…...
7.网络爬虫—正则表达式详讲
7.网络爬虫—正则表达式详讲与实战Python 正则表达式re.match() 函数re.search方法re.match与re.search的区别re.compile 函数检索和替换检索:替换:findallre.finditerre.split正则表达式模式常见的字符类正则模式正则表达式模式量词正则表达式举例前言&…...
关于位运算的巧妙性:小乖,你真的明白吗?
一.位运算的概念什么是位运算?程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。位运算就是直接操作二进制数,那么有哪些种类的位运算呢?常见的运算符有与(&)、或(|)、异或(^)、…...
【Android车载系列】第5章 AOSP开发环境配置
1 硬件支持 建议空闲内存16G以上,同时硬盘400G以上 内存不够可以使用 Linux 的交换分区2 VMware Workstation安装 https://download3.vmware.com/software/wkst/file/VMware-workstation-full-16.1.1-17801498.exe2.1 Ubuntu镜像 http://mirrors.aliyun.com/ubun…...
个人时间管理网站—Git项目管理
🌟所属专栏:献给榕榕🐔作者简介:rchjr——五带信管菜只因一枚😮前言:该专栏系为女友准备的,里面会不定时发一些讨好她的技术作品,感兴趣的小伙伴可以关注一下~👉文章简介…...
2023最新ChatGPT整理的40道Java高级面试题
2023 年最火的就是 ChatGPT 了,很多同事使用他完成一些代码上的智能提示,也有人使用它发了财《「用ChatGPT年入百万!」各博主发布生财之道,网友:答辩搬运工》、《“躺着就能赚大钱”?ChatGPT火了,有人早就动起坏脑筋》等。 最近我也使用 ChatGPT 写技术文章了,比如:《…...
单机分布式一体化是什么?真的是数据库的未来吗,OceanBase或将开启新的里程碑
一. 数据 我们先说说数据这个东西,这段时间的ChatGPT在全世界的爆火说明了一件事,数据是有用的,并且大量的数据如果有一个合适的LLM大规模语言模型训练之后,可以很高程度的完成很多意想不到的事情。 我们大多数的时候的注意力只…...
100天精通Python丨基础知识篇 —— 03、Python基础知识扫盲(第一个Python程序,13个小知识点)
文章目录🐜 1、Python 初体验Pycharm 第一个程序交互式编程第一个程序🐞 2、Python 引号🐔 3、Python 注释🦅 4、Python 保留字符🐯 5、Python 行和缩进🐨 6、Python 空行🐹 7、Python 输出&…...
springboot逍遥大药房管理系统
084-springboot逍遥大药房管理系统演示录像开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包&a…...
ZYNQ中的GPIO与AXI GPIO
GPIO GPIO—一种外设,对器件进行观测和控制MIO—将来自PS外设和静态存储器接口的访问多路复用到PS引脚上处理器控制外设的方法—通过一组寄存器包括状态寄存器和控制寄存器,这些寄存器都是有地址的,通过这些寄存器的读写进行外设的控制sessi…...
接口导入功能
1.接口api export function import(param) { return fetch({ url: XXX.import, method: POST, headers: { Content-Type: multipart/form-data; }, data: param }) } 2.页面vue 和 js逻辑 <el-button :loading"disable&qu…...
网络安全知识点总结 期末总结
1、信息安全从总体上可以分成5个层次,密码技术 是信息安全中研究的关键点。 2、握手协议 用于客户机与服务器建立起安全连接之前交换一系列信息的安全信道。 3、仅设立防火墙系统,而没有 安全策略 ,防火墙就形同虚设。 4、应用代理防火墙 …...
linux挂载远程目录
服务端操作 # 1、安装NFS程序 yum -y install nfs* rpcbind,在centos6以前自带的yum源中为portmap。 使用yum安装nfs时会下载依赖,因此只要下载nfs即可,无需再下载rpcbind. # 2、查看是否安装了nfs与rpcbind rpm -qa | grep nfs rpm -qa | grep rpc…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...
向量几何的二元性:叉乘模长与内积投影的深层联系
在数学与物理的空间世界中,向量运算构成了理解几何结构的基石。叉乘(外积)与点积(内积)作为向量代数的两大支柱,表面上呈现出截然不同的几何意义与代数形式,却在深层次上揭示了向量间相互作用的…...
32位寻址与64位寻址
32位寻址与64位寻址 32位寻址是什么? 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元(地址),其核心含义与能力如下: 1. 核心定义 地址位宽:CPU或内存控制器用32位…...
【Pandas】pandas DataFrame dropna
Pandas2.2 DataFrame Missing data handling 方法描述DataFrame.fillna([value, method, axis, …])用于填充 DataFrame 中的缺失值(NaN)DataFrame.backfill(*[, axis, inplace, …])用于**使用后向填充(即“下一个有效观测值”)…...
盲盒一番赏小程序:引领盲盒新潮流
在盲盒市场日益火爆的今天,如何才能在众多盲盒产品中脱颖而出?盲盒一番赏小程序给出了答案,它以创新的玩法和优质的服务,引领着盲盒新潮流。 一番赏小程序的最大特色在于其独特的赏品分级制度。赏品分为多个等级,从普…...
