剑指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…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
