每日一题之二分查找(一)
每日一题之二分查找(一)
1.题目(搜索插入位置)
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
2.解题思路
因为数组是有序的排列数组,且无重复元素,所以可以使用二分来找下标
这里一共有四种情况
(1)数组中找到了目标元素,返回当前目标元素的下标结束
(2)目标元素不存在,应在数组的所有元素之前
(3)目标元素不存在,应在所有的元素之后
(4)目标元素不存在,应在数组中的某个位置
具体实现步骤
1.先找到这个数组的左边界,再找到这个数组的右边界,此时的范围就是整个数组
2.然后进行二分查找
(1)先找到中间位置的那个数,然后与目标值进行比较,
1> 如果当前的数比目标值小的话那么左边界变为中间位置向右一个的位置,继续进行查找
2> 如果当前的数比目标值小的话那么右边界变为中间位置向左一个的位置,继续进行查找
3> 如果当前的数和目标值相等的话,那么找到了
(2)当左边界比右边界大的时候,结束查找
3.那要添加元素的位置就是右边界+1的位置
3.代码
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0;int right=nums.size()-1;while(left<=right){//int mid=(left+right)>>1;这里通过学习发现可以进行优化//优化如下int mid=left+(right-left)/2;//优化后的代码if(nums[mid]==target){return mid;}if(nums[mid]>target){right=mid-1;}if(nums[mid]<target){left=mid+1;}}return right+1;}
};
相关文章:
每日一题之二分查找(一)
每日一题之二分查找(一) 1.题目(搜索插入位置) 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间…...
Redisson的看门狗策略——保障Redis数据安全与稳定的机制
前言 自定义redis分布式锁无法自动续期,比如,一个锁设置了1分钟超时释放,如果拿到这个锁的线程在一分钟内没有执行完毕,那么这个锁就会被其他线程拿到,可能会导致严重的线上问题,在秒杀场景下,…...
2.2 消元法的概念
一、消元法介绍 消元法(elimination)是一个求解线性方程组的系统性方法。下面是使用消元法求解一个 2 2 2\times2 22 线性方程组的例子。消元之前,两个方程都有 x x x 和 y y y,消元后,第一个未知数 x x x 将从第…...
删除有序数组中的重复项
目录 题目: 示例: 题目分析: 解题思路: 题目: 给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的…...
【数据库】
文章目录 1. 聚合函数练习: 2. 子查询 1. 聚合函数 where中过滤条件中不能写聚合函数,有聚合函数需要写到Having中 方式一效率高: Select执行流程 练习: 2. 第七题:count(*)有问题,原因是左外连接后…...
高级深入--day38
阳光热线问政平台 http://wz.sun0769.com/index.php/question/questionType?type4 爬取投诉帖子的编号、帖子的url、帖子的标题,和帖子里的内容。 items.py import scrapyclass DongguanItem(scrapy.Item):# 每个帖子的标题title scrapy.Field()# 每个帖子的编…...
基于springboot,vue校园社团管理系统
开发工具:IDEA 服务器:Tomcat9.0, jdk1.8 项目构建:maven 数据库:mysql5.7 系统分前后台,项目采用前后端分离 前端技术:vueelementUI 服务端技术:springbootmybatis-plus 本系…...
广州华锐互动:VR虚拟现实物理学习平台,开启数字化教学新格局
随着虚拟现实(VR)技术的不断发展,越来越多的领域开始应用这一技术。广州华锐互动开发的VR虚拟现实物理学习平台就得到了广泛应用,平台涉及力学、光学、热学等初中物理知识,还包含了物理名人、实验器具、物理现象的还原和学习,相比…...
【tio-websocket】8、T-IO对半包和粘包的处理
介绍 t-io对数据的解码是在DecodeRunnable中完成的,一个TCP连接对应一个DecodeRunnable半包粘包的处理也都在DecodeRunnable中完成的关于DecodeRunnable 先贴上 DecodeRunnable 的源代码: import java.nio.BufferUnderflowException; import java.nio.ByteBuffer; import j…...
【Linux】安装与配置虚拟机及虚拟机服务器坏境配置与连接
目录 操作系统介绍 什么是操作系统 常见操作系统 UNIX操作系统 linux操作系统 mac操作系统 嵌入式操作系统 个人版本和服务器版本的区别 安装VMWare虚拟机 VMWare虚拟网卡 编辑 配置虚拟网络编辑器 编辑 安装配置Windows Server 2012 R2 安装Windows Server 2…...
Redis常识
文章目录 缓存的三个风险数据结构淘汰策略 和 过期删除策略过期删除淘汰 如何理解单线程redis特性复制gossip协议事务(和mysql不同,是不严格的事务 )集群(高可用)管道持久化 缓存的三个风险 缓存雪崩(缓存…...
Instant,LocalDate,LocalTime,LocalDateTime和ZonedDateTime
Instant 封装了从 1970-01-01T00:00:00Z 开始的秒数,相当于时间戳。 主要有两个属性: private final long seconds; private final int nanos;LocalDate 用于表示日期,包括年、月、日,例如 2017-12-03。 主要有三个属性&…...
Web入门笔记
Web入门笔记 HTTP协议 超文本传输协议 规定了浏览器和服务器之间数据传输的规则,请问数据和响应数据的格式 基于TCP请求-响应模式一次请求对应一次响应无状态的协议 请问数据格式 浏览器版本:解决浏览器兼容问题。GET请求体:存放请求参数…...
Linux网络编程二(TCP三次握手、四次挥手、TCP滑动窗口、MSS、TCP状态转换、多进程/多线程服务器实现)
TCP三次握手 TCP三次握手(TCP three-way handshake)是TCP协议建立可靠连接的过程,确保客户端和服务器之间可以进行可靠的通信。下面是TCP三次握手的详细过程: 假设客户端为A,服务器为B 1、第一次握手(SYN1,seq500&…...
C#核心笔记——(一)C#和.NET Framework
C#是一种通用的,类型安全的面向对象编程语言。其目标是提高程序员生产力。 一.面向对象 C#实现了丰富的面向对象范式,包括封装、继承、多态。 C#面向对象特性包括: 统一的类型系统 类与接口 属性、方法、事件 C#支持纯函数模式 二、类型安…...
【2023年冬季】华为OD统一考试(B卷)题库清单(已收录345题),又快又全的 B 卷题库大整理
目录 专栏导读华为OD机试算法题太多了,知识点繁杂,如何刷题更有效率呢? 一、逻辑分析二、数据结构1、线性表① 数组② 双指针 2、map与list3、队列4、滑动窗口5、二叉树6、并查集7、栈 三、算法1、基础算法① 贪心算法② 二分查找③ 分治递归…...
云服务器的先驱,亚马逊云科技海外云服务器领军者
随着第三次工业革命的发展,移动互联网技术带来的信息技术革命为我们的生活带来了极大的便捷。其中,不少优秀的云服务器产品发挥了不可低估的作用,你或许听说过亚马逊云科技、谷歌GCP、IBM Cloud等优秀的海外云服务器。那么云服务器有哪些&…...
QT webengine显示HTML简单示例
文章目录 参考示例1TestWebenqine.promainwindow.hmainwindow.cppmain.cpp效果 示例2 (使用setDevToolsPage函数)main.cpp效果 参考 QT webengine显示HTML简单示例 示例1 编译器 : Desktop Qt 5.15.2 MSVC2019 64bit编辑器: QtCreator代码: TestWebenqine.pro # TestWeben…...
Spark_SQL函数定义(定义UDF函数、使用窗口函数)
一、UDF函数定义 (1)函数定义 (2)Spark支持定义函数 (3)定义UDF函数 (4)定义返回Array类型的UDF (5)定义返回字典类型的UDF 二、窗口函数 (1&…...
【Leetcode】【每日一题】【中等】274. H 指数
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/h-index/description/?envTyped…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
在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…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
