剑指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…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
