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

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] <= 104
  • nums无重复元素升序 排列数组
  • -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]上。因此更新rightmid位置,继续查找
    • nums[mid]<target时,说明mid落在了[left,index-1]区间上,mid右边但不包括mid本身,可能是最终结果,所以我们接下来查找的区间在[mid+1,right]上。因此更新leftmid+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. 题目链接&#xff1a;35. 搜索插入位置 2. 题目描述&#xff1a; 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。…...

centos升级openssh

注意&#xff1a; openssh升级异常会造成服务失联&#xff0c;如果在允许的情况下可以安装talent服务&#xff0c;使用talent升级&#xff1b; 如果不能安装talent服务&#xff0c;可以打开多个终端&#xff0c;启动ping命令&#xff0c;防止升级终端失败后&#xff0c;作为备用…...

架构、框架、模式,极简文字介绍

1、架构、框架、模式是一种从大到小的关系&#xff0c;也是一种组合关系 2、架构一般针对一个行业或一类应用&#xff0c;是技术和应用的完美组合 3、框架比较小&#xff0c;很多表现为中间件&#xff0c;框架一般是从技术角度解决同类问题&#xff0c;从技术的横切面来解决实…...

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中好玩的数据流定向和管道命令一

知识点复习&#xff1a; 什么是数据流定向&#xff0c;个人理解就是将 一些结果信息不打印在屏幕上&#xff0c;而是定位在某一个文件里面 ll /wdf > file 会覆盖file的原内容 ll /wdf >> 会追加到原文件后面 比如在自己的目录新建1.TXT&#xff0c; 2.txt ll /…...

tesseract-ocr-w64-setup-5.3.3.20231005.exe 百度网盘下载

链接&#xff1a;https://pan.baidu.com/s/1q6u-nRvj2S8n6jSYz2iqig?pwdbtm4 提取码&#xff1a;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 框架有哪些优缺点?

目录 前言&#xff1a; 用法&#xff1a; 理解&#xff1a; 优点&#xff1a; 嵌套外部内容&#xff1a; 独立性&#xff1a; 分离安全性&#xff1a; 跨平台兼容性&#xff1a; 方便维护&#xff1a; 缺点&#xff1a; 性能开销&#xff1a; 用户体验问题&#xf…...

git 版本管理

标签管理 git tag: 标签的操作 用于给某次提交打个标签 命令&#xff1a;git tag B08P09 为当前提交打上 B08P09 的标签 命令&#xff1a;git tag B08P09 ab1591eb4e06c1e93fdd50126b9fab8a88d89155 为这个节点打上 B08P09 的标签 命令&#xff1a;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问题】最大正方形

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是【动态规划】&#xff0c;使用【数组】这个基本的数据结构来实现&#xff0c;这个高频题的站点是&#xff1a;CodeTop&#xff0c;筛选条件为&…...

20.Node-Express框架的用法

题记 node.js中express框架的用法 Express框架的特点 可以设置中间件来响应 HTTP 请求。 定义了路由表用于执行不同的 HTTP 请求动作。 可以通过向模板传递参数来动态渲染 HTML 页面。 安装Express模块 npm install express --save 安装重要模块 npm install body-parser --…...

cuda卸载

去查看你的电脑显卡对应的cuda版本&#xff0c;不然还是一整个用不到gpu的情况嘿嘿. 啊啊啊啊打开控制面板看一下&#xff0c;驱动不要乱卸载&#xff1a; 这些东西不能全部卸载了哦&#xff0c;只能卸载含有“CUDA”的那几个&#xff08;其实其他的可能也没有用 但是不懂的哇 …...

怎么选择好的游戏平台开发商?

选择好的游戏平台开发商需要考虑以下几个方面&#xff1a; 开发经验 了解游戏开发公司的历史和经验是找到靠谱公司的重要步骤。查看公司的官方网站、社交媒体账号等渠道&#xff0c;了解公司的发展历程、团队规模、客户案例等。同时&#xff0c;了解公司是否有相关的游戏开发经…...

OSATE 插件 Cheddar 的安装与简单使用

一、Cheddar简介 Cheddar是一个开源的实时系统任务调度模拟器/分析仪&#xff0c;可以使用Cheddar进行任务的可调度性分析以及相关的性能分析。对于Cheddar的详细信息可以参考其官网&#xff1a; Cheddar - open-source real-time scheduling simulator/analyzer (univ-brest…...

解决:vscode和jupyter远程连接无法创建、删除文件的问题(permission denied)

目录 问题&#xff1a;vscode和jupyter远程连接服务器无法创建、删除文件的问题原因&#xff1a;代码文件的权限不够解决方法&#xff1a;1.ls -l查看目录所在组&#xff0c;权限2.chown修改拥有者和所在组 问题&#xff1a;vscode和jupyter远程连接服务器无法创建、删除文件的…...

Android Studio模拟器/虚拟设备连接互联网的方法

如图&#xff0c;无线、网络都无法联网 找到本机的DNS 找到emu-launch-params.txt&#xff0c;添加DNS -dns-server 192.168.124.1 重启虚拟机&#xff0c;关闭无线...

linux 内存检测工具 kfence 详解

版本基于&#xff1a; Linux-5.10 约定&#xff1a; PAGE_SIZE&#xff1a;4K 内存架构&#xff1a;UMA 0. 前言 本文 kfence 之外的代码版本是基于 Linux5.10&#xff0c;最近需要将 kfence 移植到 Linux5.10 中&#xff0c;本文借此机会将 kfence 机制详细地记录一下。 k…...

虚拟机VMware Workstation Pro安装配置使用服务器系统ubuntu-22.04.3-live-server-amd64.iso

虚拟机里安装ubuntu-23.04-beta-desktop-amd64开启SSH(换源和备份)配置中文以及中文输入法等 ​一、获取Ubuntu服务器版 获取Ubuntu服务器版 二、配置虚拟机 选择Custom(advanced)&#xff1a; 选择Workstation 17.x: 选择“I will install the operating system later.”…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...