当前位置: 首页 > 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…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...