Leetcode刷题详解——搜索插入位置
1. 题目链接:35. 搜索插入位置
2. 题目描述:
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
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
3. 算法思路(二分查找)
-
设插入坐标为
index,根据插入位置的特点可以知道:[left,index-1]内所有元素均是小于target的[index,right]内所有元素均是大于等于target的
-
设
left为左边界,right为有边界,根据mid位置的信息,决定下一轮的区间范围:- 当
nums[mid]>=target时,说明mid落在了[index,right]区间上,mid包括mid本身,可能是最终结果,所以我们接下来查找的区间在[left,mid]上。因此更新right到mid位置,继续查找 - 当
nums[mid]<target时,说明mid落在了[left,index-1]区间上,mid右边但不包括mid本身,可能是最终结果,所以我们接下来查找的区间在[mid+1,right]上。因此更新left到mid+1的位置,继续查找
- 当
-
直到我们的查找结果的长度变为
1,也就是left==right的时候,left或者right所在的位置就是我们要找的结果

4. C++算法代码
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid;}}if(nums[left]<target) return right+1;return right;}
};
相关文章:
Leetcode刷题详解——搜索插入位置
1. 题目链接:35. 搜索插入位置 2. 题目描述: 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。…...
centos升级openssh
注意: openssh升级异常会造成服务失联,如果在允许的情况下可以安装talent服务,使用talent升级; 如果不能安装talent服务,可以打开多个终端,启动ping命令,防止升级终端失败后,作为备用…...
架构、框架、模式,极简文字介绍
1、架构、框架、模式是一种从大到小的关系,也是一种组合关系 2、架构一般针对一个行业或一类应用,是技术和应用的完美组合 3、框架比较小,很多表现为中间件,框架一般是从技术角度解决同类问题,从技术的横切面来解决实…...
Java实现Fisher‘s Exact Test 的置信区间的计算
实现代码 package com.bgi.aigi.common.utils;public class FisherExactUtils {public static double[] getConfidenceInterval(double[][] data) {if (datanull||data.length!2||data[0].length!2||data[1].length!2) {return null;}double[] intervalnew double[2];double …...
YOLOv8改进:全网原创首发 | 新颖的多尺度卷积注意力(MSCA),即插即用,助力小目标检测 | NeurIPS2022
💡💡💡本文全网首发独家改进:多尺度卷积注意力(MSCA),有效地提取上下文信息,新颖度高,创新十足。 1)作为注意力MSCA使用; 推荐指数:五星 MSCA | 亲测在多个数据集能够实现涨点,多尺度特性在小目标检测表现也十分出色。 💡💡💡Yolov8魔术师,独家首发…...
linux中好玩的数据流定向和管道命令一
知识点复习: 什么是数据流定向,个人理解就是将 一些结果信息不打印在屏幕上,而是定位在某一个文件里面 ll /wdf > file 会覆盖file的原内容 ll /wdf >> 会追加到原文件后面 比如在自己的目录新建1.TXT, 2.txt ll /…...
tesseract-ocr-w64-setup-5.3.3.20231005.exe 百度网盘下载
链接:https://pan.baidu.com/s/1q6u-nRvj2S8n6jSYz2iqig?pwdbtm4 提取码:btm4...
Linux环境下Redis 集群部署
Linux环境下Redis 集群部署 1.单机Redis部署2.Redis 集群配置2.1 创建redis集群安装目录2.2 将redis单机部署目录下的redis.confi文件复制到每个目录下2.3 修改每个文件夹下的redis.conf2.4 修改完六个配置内容后开始启动2.5 启动完后查看进程2.6 建集群 1.单机Redis部署 Linu…...
html iframe 框架有哪些优缺点?
目录 前言: 用法: 理解: 优点: 嵌套外部内容: 独立性: 分离安全性: 跨平台兼容性: 方便维护: 缺点: 性能开销: 用户体验问题…...
git 版本管理
标签管理 git tag: 标签的操作 用于给某次提交打个标签 命令:git tag B08P09 为当前提交打上 B08P09 的标签 命令:git tag B08P09 ab1591eb4e06c1e93fdd50126b9fab8a88d89155 为这个节点打上 B08P09 的标签 命令:git tag -a <tagname>…...
hyperf框架接入pgsql扩展包
文章目录 hyperf2.2安装 hyperf3.0安装 配置 环境版本支持 hyperf框架版本php版本database版本2.2>7.4~2.2.03.0>8.1~3.0.0 hyperf2.2 https://github.com/hyperf/database-pgsql-incubator 安装 hyperf/database 组件版本必须大于等于 v2.2.26 composer require hype…...
【算法训练-动态规划 五】【二维DP问题】最大正方形
废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【动态规划】,使用【数组】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为&…...
20.Node-Express框架的用法
题记 node.js中express框架的用法 Express框架的特点 可以设置中间件来响应 HTTP 请求。 定义了路由表用于执行不同的 HTTP 请求动作。 可以通过向模板传递参数来动态渲染 HTML 页面。 安装Express模块 npm install express --save 安装重要模块 npm install body-parser --…...
cuda卸载
去查看你的电脑显卡对应的cuda版本,不然还是一整个用不到gpu的情况嘿嘿. 啊啊啊啊打开控制面板看一下,驱动不要乱卸载: 这些东西不能全部卸载了哦,只能卸载含有“CUDA”的那几个(其实其他的可能也没有用 但是不懂的哇 …...
怎么选择好的游戏平台开发商?
选择好的游戏平台开发商需要考虑以下几个方面: 开发经验 了解游戏开发公司的历史和经验是找到靠谱公司的重要步骤。查看公司的官方网站、社交媒体账号等渠道,了解公司的发展历程、团队规模、客户案例等。同时,了解公司是否有相关的游戏开发经…...
OSATE 插件 Cheddar 的安装与简单使用
一、Cheddar简介 Cheddar是一个开源的实时系统任务调度模拟器/分析仪,可以使用Cheddar进行任务的可调度性分析以及相关的性能分析。对于Cheddar的详细信息可以参考其官网: Cheddar - open-source real-time scheduling simulator/analyzer (univ-brest…...
解决:vscode和jupyter远程连接无法创建、删除文件的问题(permission denied)
目录 问题:vscode和jupyter远程连接服务器无法创建、删除文件的问题原因:代码文件的权限不够解决方法:1.ls -l查看目录所在组,权限2.chown修改拥有者和所在组 问题:vscode和jupyter远程连接服务器无法创建、删除文件的…...
Android Studio模拟器/虚拟设备连接互联网的方法
如图,无线、网络都无法联网 找到本机的DNS 找到emu-launch-params.txt,添加DNS -dns-server 192.168.124.1 重启虚拟机,关闭无线...
linux 内存检测工具 kfence 详解
版本基于: Linux-5.10 约定: PAGE_SIZE:4K 内存架构:UMA 0. 前言 本文 kfence 之外的代码版本是基于 Linux5.10,最近需要将 kfence 移植到 Linux5.10 中,本文借此机会将 kfence 机制详细地记录一下。 k…...
虚拟机VMware Workstation Pro安装配置使用服务器系统ubuntu-22.04.3-live-server-amd64.iso
虚拟机里安装ubuntu-23.04-beta-desktop-amd64开启SSH(换源和备份)配置中文以及中文输入法等 一、获取Ubuntu服务器版 获取Ubuntu服务器版 二、配置虚拟机 选择Custom(advanced): 选择Workstation 17.x: 选择“I will install the operating system later.”…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
