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

剑指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-二维数组中的查找

文章目录题目描述题解一 无脑暴力循环题解二 初始二分法&#x1f315;博客x主页&#xff1a;己不由心王道长&#x1f315;! &#x1f30e;文章说明&#xff1a;剑指offer-二维数组中的查找&#x1f30e; ✅系列专栏&#xff1a;剑指offer &#x1f334;本篇内容&#xff1a;对剑…...

怎么设计一个秒杀系统

1、系统部署 秒杀系统部署要单独区别开其他系统单独部署&#xff0c;这个系统的流量肯定很大&#xff0c;单独部署。数据库也要单独用一个部署的数据库或者集群&#xff0c;防止高并发导致整个网站不可用。 2、防止超卖 100个库存&#xff0c;1000个人买&#xff0c;要保证不…...

程序参数解析C/C++库 The Lean Mean C++ Option Parser

开发中我们经常使用程序参数&#xff0c;根据参数的不同来实现不同的功能。POSIX和GNU组织对此都制定了一些标准&#xff0c;为了我们程序更为通用标准&#xff0c;建议遵循这些行业内的规范&#xff0c;本文介绍的开源库The Lean Mean C Option Parser就可以很好满足我们的需求…...

Java中的深拷贝和浅拷贝

目录 &#x1f34e;引出拷贝 &#x1f34e;浅拷贝 &#x1f34e;深拷贝 &#x1f34e;总结 引出拷贝 现在有一个学生类和书包类&#xff0c;在学生类中有引用类型的书包变量&#xff1a; class SchoolBag {private String brand; //书包的品牌private int size; //书…...

大文件上传

上图就是大致的流程一、标题图片上传课程的标题图片Ajax发送请求到后端后端接收到图片使用IO流去保存图片&#xff0c;返回图片的信息对象JS回调函数接收对象通过$("元素id").val(值)&#xff0c;方式给页面form表达img标签src属性值&#xff0c;达到上传图片并回显二…...

Python每日一练(20230327)

目录 1. 最大矩形 &#x1f31f;&#x1f31f;&#x1f31f; 2. 反转链表 II &#x1f31f;&#x1f31f; 3. 单词接龙 II &#x1f31f;&#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏 C/C每日…...

Centos7 升级内核到5.10mellanox 编译安装

升级5.10内核 #uname -r 重启后 进入新的内核 进入新的内核信息 直接查看是看不到gcc版本 5.10需要高版本gcc 才可以进行编译...

冯诺依曼,操作系统以及进程概念

文章目录一.冯诺依曼体系结构二.操作系统&#xff08;operator system&#xff09;三.系统调用和库函数四.进程1.进程控制块&#xff08;PCB&#xff09;2.查看进程3.系统相关的调用4.fork介绍&#xff08;并发引入&#xff09;五.总结一.冯诺依曼体系结构 计算机大体可以说是…...

7.网络爬虫—正则表达式详讲

7.网络爬虫—正则表达式详讲与实战Python 正则表达式re.match() 函数re.search方法re.match与re.search的区别re.compile 函数检索和替换检索&#xff1a;替换&#xff1a;findallre.finditerre.split正则表达式模式常见的字符类正则模式正则表达式模式量词正则表达式举例前言&…...

关于位运算的巧妙性:小乖,你真的明白吗?

一.位运算的概念什么是位运算&#xff1f;程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。位运算就是直接操作二进制数&#xff0c;那么有哪些种类的位运算呢&#xff1f;常见的运算符有与(&)、或(|)、异或(^)、…...

【Android车载系列】第5章 AOSP开发环境配置

1 硬件支持 建议空闲内存16G以上&#xff0c;同时硬盘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项目管理

&#x1f31f;所属专栏&#xff1a;献给榕榕&#x1f414;作者简介&#xff1a;rchjr——五带信管菜只因一枚&#x1f62e;前言&#xff1a;该专栏系为女友准备的&#xff0c;里面会不定时发一些讨好她的技术作品&#xff0c;感兴趣的小伙伴可以关注一下~&#x1f449;文章简介…...

2023最新ChatGPT整理的40道Java高级面试题

2023 年最火的就是 ChatGPT 了,很多同事使用他完成一些代码上的智能提示,也有人使用它发了财《「用ChatGPT年入百万!」各博主发布生财之道,网友:答辩搬运工》、《“躺着就能赚大钱”?ChatGPT火了,有人早就动起坏脑筋》等。 最近我也使用 ChatGPT 写技术文章了,比如:《…...

单机分布式一体化是什么?真的是数据库的未来吗,OceanBase或将开启新的里程碑

一. 数据 我们先说说数据这个东西&#xff0c;这段时间的ChatGPT在全世界的爆火说明了一件事&#xff0c;数据是有用的&#xff0c;并且大量的数据如果有一个合适的LLM大规模语言模型训练之后&#xff0c;可以很高程度的完成很多意想不到的事情。 我们大多数的时候的注意力只…...

100天精通Python丨基础知识篇 —— 03、Python基础知识扫盲(第一个Python程序,13个小知识点)

文章目录&#x1f41c; 1、Python 初体验Pycharm 第一个程序交互式编程第一个程序&#x1f41e; 2、Python 引号&#x1f414; 3、Python 注释&#x1f985; 4、Python 保留字符&#x1f42f; 5、Python 行和缩进&#x1f428; 6、Python 空行&#x1f439; 7、Python 输出&…...

springboot逍遥大药房管理系统

084-springboot逍遥大药房管理系统演示录像开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&a…...

ZYNQ中的GPIO与AXI GPIO

GPIO GPIO—一种外设&#xff0c;对器件进行观测和控制MIO—将来自PS外设和静态存储器接口的访问多路复用到PS引脚上处理器控制外设的方法—通过一组寄存器包括状态寄存器和控制寄存器&#xff0c;这些寄存器都是有地址的&#xff0c;通过这些寄存器的读写进行外设的控制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个层次&#xff0c;密码技术 是信息安全中研究的关键点。 2、握手协议 用于客户机与服务器建立起安全连接之前交换一系列信息的安全信道。 3、仅设立防火墙系统&#xff0c;而没有 安全策略 &#xff0c;防火墙就形同虚设。 4、应用代理防火墙 …...

linux挂载远程目录

服务端操作 # 1、安装NFS程序 yum -y install nfs* rpcbind,在centos6以前自带的yum源中为portmap。 使用yum安装nfs时会下载依赖&#xff0c;因此只要下载nfs即可&#xff0c;无需再下载rpcbind. # 2、查看是否安装了nfs与rpcbind rpm -qa | grep nfs rpm -qa | grep rpc…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架

1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...

Shell 解释器​​ bash 和 dash 区别

bash 和 dash 都是 Unix/Linux 系统中的 ​​Shell 解释器​​&#xff0c;但它们在功能、语法和性能上有显著区别。以下是它们的详细对比&#xff1a; ​​1. 基本区别​​ ​​特性​​​​bash (Bourne-Again SHell)​​​​dash (Debian Almquist SHell)​​​​来源​​G…...