【Leetcode】【简单】35. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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] <= 104
nums 为无重复元素 的 升序 排列数组
-104 <= target <= 104
解题思路:
- 看到排序数组基本就可以知道考察二分搜索了。
- 如果找到目标值,返回其索引,那么当
target == nums[mid]
,直接return mid;
就可以了。 - 如果目标值不存在于数组中,返回它将会被按顺序插入的位置。这等价于输出小于target的元素的数目。所以最后
return left;
或return right;
都可以。以下例子可以帮助理解:
对于 nums = [1.3.5.6], target = 2,其搜索过程如下:
- left = 0, right = 4, mid = 2, nums[mid] = 5, target<nums[mid], right = 2;搜索范围为 [0,4)
- left = 0, right = 2, mid = 1, nums[mid] =3, target<nums[mid] , right = 1;搜索范围为[0,2)
- left = 0, right = 1, mid = 0, nums[mid] = 1, nums[mid] < target ,left = 1;搜索范围为[0,1)
- left = right = 1, 结束循环
代码:
class Solution {public int searchInsert(int[] nums, int target) {return findTarget(nums, target);}int findTarget(int[] nums, int target){int left = 0, right = nums.length;while(left < right){int mid = left + (right - left)/2;if(target == nums[mid])return mid;else if(target < nums[mid])right = mid;else if(target > nums[mid])left = mid + 1;}return left; // return right;}
}
测试结果:
相关文章:
【Leetcode】【简单】35. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出: 2 示例 2: 输入:…...
sql面试题
mysql优化 优化准则: 建表时:合理选择字段的类型,单表字段数量 sql查询尽量单表操作,避免复杂操作,复杂的多表通过java代码实现 构建复合索引优化,索引尽量可以覆盖主要业务查询 sql避免索引失效 避免大…...
SQL 进阶刷题笔记
SQL 进阶刷题笔记 一、MySQL 进阶 这里主要是 MySQL 刷题相关笔记,方便后面温习和查阅,希望可以帮到大家!!! 题1 请计算每张SQL类别试卷发布后,当天5级以上的用户作答的人数uv和平均分avg_score࿰…...
[网鼎杯 2020 朱雀组]Think Java
SqlDict.java ,其中sql语句处存在sql注入漏洞 package .sqldict;import cn.abc.core.sqldict.Row; import cn.abc.core.sqldict.Table; import java...
AIR32F103(十) 在无系统环境和FreeRTOS环境集成LVGL
目录 AIR32F103(一) 合宙AIR32F103CBT6开发板上手报告AIR32F103(二) Linux环境和LibOpenCM3项目模板AIR32F103(三) Linux环境基于标准外设库的项目模板AIR32F103(四) 27倍频216MHz,CoreMark跑分测试AIR32F103(五) FreeRTOSv202112核心库的集成和示例代码AIR32F103(六) ADC,I2S…...
SpringBoot接口 - 如何统一异常处理
SpringBoot接口如何对异常进行统一封装,并统一返回呢?以上文的参数校验为例,如何优雅的将参数校验的错误信息统一处理并封装返回呢?为什么要优雅的处理异常如果我们不统一的处理异常,经常会在controller层有大量的异常…...
如何使用Python进行数据可视化
数据可视化是一种将数据呈现为图形或图表的技术,它有助于理解和发现数据中的模式和趋势。Python是一种流行的编程语言,有很多库可以帮助我们进行数据可视化。在本文中,我们将介绍使用Python进行数据可视化的基本步骤。 第一步:导…...
vue -- 自定义指令钩子函数补充 自定义过滤器filter参数
自定义指令补充 自定义指令通过钩子函数的形式来实现自定义的功能 这里是几个常用的钩子函数以及它的方法: bind:只调用一次,指令第一次绑定到元素时调用,在这里可以进行一次性的初始化设置。 inserted:被绑定元素插…...
Qt不会操作?Qt原理不知道? | Qt详细讲解
文章目录Qt界面开发必备知识UI界面与控件类型介绍Qt设计器原理控件类型的介绍信号与槽机制处理常用控件创建与设置常见展示型控件创建与设置常见动作型控件创建与设置常见输入型控件创建与设置常见列表控件创建于设置Qt中对象树的介绍项目源码结构刨析.pro.hmain.cpp.cppQt界面…...
LeetCode-面试题 17.05. 字母与数字【前缀和,哈希表】
LeetCode-面试题 17.05. 字母与数字【前缀和,哈希表】题目描述:解题思路一:前缀和。数字为-1,字母为1。我们需要找到的子数组是前缀和之差为0的,例如s[right]-s[left]0,那么s[right]s[left],变为…...
华为OD机试题 - 叠放书籍(JavaScript)| 机考必刷
更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:叠放书籍题目输入输出示例一输入输出Code解题思路版权说明华为O…...
【数据库概论】第十一章 数据库并发控制
第十一章 并发控制 在多处理机系统中,每个处理机可以运行一个事务,多个处理机可以同时运行多个事务,实现多个事务并行运行,这就是同时并发方式。当多个用户并发存取数据库时会产生多个事务同时存取同一事务的情况,如果…...
Nginx配置实例-反向代理案例二
实现效果:使用nginx反向代理,根据访问的路径跳转到不同端口服务 nginx监听端口为9000, 访问 http://127.0.0.1:9000/edu/ 直接跳转到127.0.0.1:8080 访问 http://127.0.0.1:9000/vod/ 直接跳转到127.0.0.1:8081 一、准备工作 1. 准备两个tom…...
HTML 字符集
为了正确显示 HTML 页面,Web 浏览器必须知道要使用哪个字符集。 从 ASCII 到 UTF-8 ASCII 是第一个字符编码标准。ASCII 定义了 128 种可以在互联网上使用的字符:数字(0-9)、英文字母(A-Z)和一些特殊字符…...
【C语言】每日刷题 —— 牛客语法篇(3)
前言 大家好,继续更新专栏c_牛客,不出意外的话每天更新十道题,难度也是从易到难,自己复习的同时也希望能帮助到大家,题目答案会根据我所学到的知识提供最优解。 🏡个人主页:悲伤的猪大肠9的博客…...
基于Vue3和element-plus实现一个完整的登录功能
先看一下最终要实现的效果:登录页面:注册页面:(1)引入element-plus组件库引入组件库的方式有好多种,在这里我就在main.js全局引入了.npm i element-plus -Smain.js中代码:import { createApp } from "vue"; //element-plus import ElementPlus from "element-pl…...
【java】Java 中泛型的实现原理
文章目录前序1. 泛型1.1 泛型方法1.2 泛型类1.3 泛型接口2. 泛型的基本原理3. 小结前序 泛型是 Java 开发中常用的技术,了解泛型的几种形式和实现泛型的基本原理,有助于写出更优质的代码。本文总结了 Java 泛型的三种形式以及泛型实现原理。 1. 泛型 …...
【C++提高编程】C++全栈体系(二十七)
C提高编程 第五章 STL- 常用算法 三、常用排序算法 算法简介: sort //对容器内元素进行排序random_shuffle //洗牌 指定范围内的元素随机调整次序merge // 容器元素合并,并存储到另一容器中reverse // 反转指定范围的元素 1. sort 功能描述&#…...
软考高级信息系统项目管理师系列之三十九:项目集管理
软考高级信息系统项目管理师系列之三十九:项目集管理 一、项目集管理内容二、项目集管理基础概述1.项目集定义2.项目集活动3.项目集管理三、项目集的管理过程四、项目集治理1.项目集治理概述2.项目集指导委员会的职责3.项目集治理功能五、项目集生命周期1.项目集生命周期三个阶…...
44-Golang中的channel
Golang中的channel为什么要使用channelchannel的介绍channel的基本使用定义/声明channel管道的遍历和关闭channel的关闭channel的遍历goroutine和channel结合应用实例1应用实例2案例注意事项为什么要使用channel 前面使用全局变量加锁同步来解决goroutine的通讯,但…...
80/20法则
80/20法则(The 80/20 Rule)又称为帕累托法则(Pareto Principle)、二八定律、帕累托定律、最省力法则、不平衡原则、犹太法则、马特莱法则等一、什么是80/20法则80/20法则(The 80/20 Rule),又称为帕累托法则…...
计算机网络高频面试题(四)
一、什么是计算机网络 是一个将分散的、具有独立功能的计算机系统,通过通信设备与线路连接起来,由功能完善的软件实现资源共享和信息传递的系统 按分布范围,计算机网络里有局域网LAN和广域网WAN, 其中局域网的代表以太网,以及这…...
[计算机组成原理(唐朔飞 第2版)]第三章 系统总线(学习复习笔记)
3.1 总线的基本概念 计算机系统的五大部件之间的互连方式有两种 各部件之间使用单独的连线,称为分散连接将各部件连到一组公共信息传输线上,称为总线连接 总线是连接多个部件的信息传输线,是各部件共享的传输介质。 当多个部件与总线相连时&…...
华为OD机试题 - 计算堆栈中的剩余数字(JavaScript)| 机考必刷
更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:计算堆栈中的剩余数字题目输入输出描述示例一输入输出说明示例二…...
VB实现点爆炸效果
需在窗体放置以下 4 个控件,所有控件不用设置任何属性,均采用默认设置: ’ Picture1,Command1,Check1,Timer1 Option Explicit Dim I Dim ctD() As tyD, ctDs As Long, ctR As Single Private Type tyD x…...
ICG-alkyne,吲哚菁绿-炔基结构式,实验室科研试剂,CAS号:1622335-41-4
ICG-alkyne,吲哚菁绿-炔基 中文名称:吲哚菁绿-炔基 CAS号:1622335-41-4 英文名称:ICG-alkyne 英文别名:ICG-alk 性状:绿色粉末 化学式:C48H53N3O4S 分子量:768.03 溶剂:溶于…...
【并发编程】volatile的原理我好像又懂了
文章目录优秀引用1、概述2、可见性保证2.1、什么是可见性2.2、例子举证2.3、结果解析3、有序性保证3.1、什么是有序性3.2、什么是重排序3.3、例子举证4、无法保证原子性4.1、什么是原子性4.2、例子举证5、内存屏障5.1、什么是内存屏障5.2、不同内存屏障的作用6、volatile和sync…...
【已更新实例】Java网络爬虫-HttpClient工具类
关于用Java进行爬虫的资料网上实在少之又少,但作为以一名对Java刚刚初窥门径建立好兴趣的学生怎么能静得下心用新学的Python去写,毕竟Java是世界上最好的语言嘛 (狗头)关于Java爬虫最受欢迎的一个框架Jsoup常常搭配HttpClient来使用,因为Jsou…...
7.2 向量的坐标
🙌作者简介:数学与计算机科学学院出身、在职高校高等数学专任教师,分享学习经验、生活、 努力成为像代码一样有逻辑的人! 🌙个人主页:阿芒的主页 ⭐ 高等数学专栏介绍:本专栏系统地梳理高等数学…...
公式编写1000问21-22
21.问: 求助——(周,日,60分钟,30分钟)MACD同时向上的公式怎么表达 答(知无不言): z:“macd.dea#week”; r:“macd.dea#day”; f:“macd.dea#min60”; f1:“macd.dea#min30”; rz:“macd.dea##week”; rr:“macd.dea##day”; rf:“…...
wordpress 媒体库外链/免费自己建网页
#trendsSwiper{.swiper-pagination-bullet-active,.swiper-pagination-bullet {width:48px;height: 4px;border-radius: 2px;background-color: #000000;opacity: .18;}.swiper-pagination-bullet-active{background-color: #006BE6;opacity: 1;}}...
网站正在建设中中文模板/网络宣传怎么做
这篇是在下周一写的(2013-01-28),写迟了一天,不过以后都会按时完成的。 这周不算太忙,还是很轻松的,工作上主要是开始开发新功能了,需求上的理解花费的时间比较多一点,不过你如果认真,细心&…...
咋么做进网站跳转加群/seo解释
转载自:第二十三课 阴影贴图(一) 背景 阴影和光是紧密联系在一起的,因为如果你想要产生一个阴影就必须要光。有许多的技术可以生成阴影,在接下来的两个章节中我们将学习其中的一种比较基础简单的技术-阴影贴图。 当光…...
流浪动物网站开发/深圳做网站的
Guava是google公司开发的一款Java类库扩展工具包 文档 https://github.com/google/guavahttps://github.com/google/guava/wikihttps://guava.dev/releases/snapshot-jre/api/docs/https://mvnrepository.com/artifact/com.google.guava/guava maven 依赖 <dependency&g…...
免费发布信息网站网址大全/百度竞价seo排名
2010/7/24 14:44:47 周末受到一点挫折,昨天回家打开《战争机器》把电脑海扁了一顿,心里觉得无比畅快。爽完以后感到有些失落,于是开始反思。 最近玩游戏太多了,该振作起来了,这1年多人很不在状态,很多打算做…...
徐汇网站设计/会计培训班有用吗
愿你我相遇,皆有所获! 欢迎关注微信公众号:【伤心的辣条】 免费领取一份216页软件测试工程师面试宝典文档资料。以及相对应的视频学习教程免费分享!好多小伙伴都是从功能测试入门的,从最开始或者更长的时间一直都在从事…...