LeetCode | 数组 | 二分查找 | 35.搜索插入位置【C++】
题目链接
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
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
分析思路
- 前提:有序数组+数组中无重复元素(一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的)
- 确认方法:二分查找法
- 注:二分法中关于区间的定义一般为两种——“左闭右闭[left, right]” 或 “左闭右开[left, right)”
代码实现
实现一:左闭右闭
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 左闭右闭while (left <= right){ // 当left==right,区间[left, right]依然有效,所以用<=int middle = left + ((right - left) / 2); // 防止溢出if (nums[middle] > target){ // target在左区间 [left, middle-1]right = middle - 1;} else if (nums[middle] < target){ // target在右区间 [middle+1, right]left = middle + 1;} else { // nums[middle] == targetreturn middle; // 找到目标值,直接返回下标}}// 1.目标值在数组所有元素之前 [0, -1]// 2.目标值插入数组中的位置 [left, right]// 3.目标值在数组所有元素之后 [nums.size(), nums.size()-1]return right + 1;// return left;}
};
实现二:左闭右开
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 左闭右开while (left < right){ // 当left==right,区间[left, right)无效int middle = left + ((right - left) / 2); // 防止溢出// int middle = left + ((right - left) >> 1); // >>按位右移运算符,等同于变量除以2if (nums[middle] > target){ // target在左区间 [left, middle)right = middle;} else if (nums[middle] < target){ // target在右区间 [middle+1, right)left = middle + 1;} else { // nums[middle] == targetreturn middle; // 找到目标值,直接返回下标}}// 1.目标值在数组所有元素之前 [0, 0)// 2.目标值插入数组中的位置 [left, right)// 3.目标值在数组所有元素之后 [nums.size(), nums.size() )return right;// return left;}
};
参考来源:代码随想录
补充:位移运算符为何能将数据乘以或除以 ?
按位右移运算符(>>)将变量除以;按位左移运算符(<<)将变量乘以。
例如:
变量num的值为16,其二进制表示为10000。将num右移1位,结果为01000,即8,这相当于将其减半;将num右移两位,变成了00100,即4,相当于计算num的1/4。向左移1位时结果为100000,即32,向左移两位的结果为1000000,即64,相当于计算num的2倍和4倍。
相关文章:
LeetCode | 数组 | 二分查找 | 35.搜索插入位置【C++】
题目链接 题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出…...
Linux 给网卡配置ip
ip addr | grep eth9 ifconfig eth9 10.0.0.2 netmask 255.255.255.0 up...
【C语言】翻译环境与运行环境
一、前言 在我们学习C语言的时候,第一个接触的程序就是:在屏幕上打印” hello word! “,可当时的我们却未去深入的理解与感悟,一个程序代码是如何运行的;而这一期的博客,则是带着我们,通过C代码…...
ubuntu20.04执行sudo apt-get update失败的解决方法
参考:执行sudo apt-get update失败的解决方案 1、换源型错误 (1)编辑/etc/apt/sources.list文件 在命令行中输入: sudo vim /etc/apt/sources.list 或者 sudo gedit /etc/apt/sources.list 推荐使用后者 (2…...
接口调用成功后端却一直返回404
vuespringboot 我在vue.config.js中配置了向后端的反向代理 然后使用了axios向后端发送post请求 可以看到可以接收到前端传来的值 但是前端控制台却报了 “xhr.js:245POST http://localhost:7777/api/login 404 (Not Found)” 最后询问我那智慧的堂哥... ... 解决办法是把C…...
【Vmware】 debian 12 安装教程
1.前提说明 VMware 17.5.1 (自行安装),参考Debian 12maven 3.8.7git 2.39.2jdk 1.8 / 11 / 17 1.1.Debian 下载 访问(https://www.debian.org/download) 下载 Debian 这是 Debian 12,代号为 bookworm,网络安装,用于 64 位 PC&a…...
YooAssets 使用相关
## 使用 YooAssets 动态加载原生文件时候 > 原生文件:txt;json;等需要直接保存文件内string字符的文件 需要将打包方式设置成为,PackRawFile 并且加载时候使用 API : YooAssets.LoadRawFileSync()YooAssets.LoadRa…...
精准扶贫管理系统|基于Springboot的精准扶贫管理系统设计与实现(源码+数据库+文档)
精准扶贫管理系统目录 目录 基于Springboot的精准扶贫管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员模块的实现 (1)用户信息管理 (2)贫困户信息管理 (3)新闻类型管理 &a…...
Flutter与iOS和Android原生页面交互
一、Flutter 与原生页面交互的重要性和应用场景 Flutter 是一个由 Google 开发的开源框架,用于创建跨平台的移动、Web 和桌面应用程序。Flutter 允许开发者使用一套代码库为 Android 和 iOS 等平台构建美观、高性能的应用程序。然而,尽管 Flutter 提供了…...
Chrome安装Vue插件vue-devtools
直接通过网站: Home | Vue Devtools (vuejs.org) chrome扩展商城中搜索:Vue.js devtools 参考下面edge扩展商城的图,两者流程相近...
内存和网卡压力测试
1.内存压力测试 1.1测试目的 内存压力测试的目的是评估开发板中的内存子系统性能和稳定性,以确保它能够满足特定的应用需求。开发板通常用于嵌入式系统、物联网设备、嵌入式智能家居等场景,这些场景对内存的要求通常比较高。 其内存压力测试的主要目的…...
法律行业案例法模型出现,OPenAI公布与法律AI公司Harvey合作案例
Harvey与OpenAl合作,为法律专业人士构建了一个定制训练的案例法模型。该模型是具有复杂推理广泛领域知识以及超越单一模型调用能力的任务的AI系统,如起草法律文件、回答复杂诉讼场景问题以及识别数百份合同之间的重大差异。 Harvey公司由具有反垄断和证…...
详解Qt网络编程
Qt的网络编程能力非常强大,它提供了从底层socket API到高层HTTP、FTP等协议处理的完整解决方案。下面将简要介绍Qt中网络编程的核心类及其功能,并给出一些基本的使用示例。 核心网络类: QTcpSocket 和 QTcpServer QTcpSocket 是用于TCP通信的…...
docker版Elasticsearch安装,ik分词器安装,用户名密码配置,kibana安装
1、安装es和ik分词器 创建映射目录并赋予权限: mkdir -p /docker_data/elasticsearch/conf mkdir -p /docker_data/elasticsearch/data mkdir -p /docker_data/elasticsearch/plugins chmod -R 777 /docker_data/elasticsearch编写配置文件: vi /dock…...
Python中的Requests库:HTTP请求的简单之道
目录 一、安装Requests库 二、发送请求 2.1 GET请求 2.2 POST请求 2.3 其他HTTP方法 三、处理响应 3.1 状态码 3.2 响应内容 3.3 自定义请求头 3.4 更多响应对象属性和方法 四、错误处理 五、高级请求 5.1 会话对象 5.2 SSL证书验证 5.3 设置代理 Http/Https代…...
[RK3566-Android11] 关于 a2dpsink -蓝牙支持接收播放/无PIN码连接
问题描述 1.蓝牙支持接收播放 2.蓝牙支持无PIN码连接(不需要弹出pin配对码请求弹窗) 3.蓝牙支持播放歌曲信息并应用层获取 解决方案: 1.a2dpsink-蓝牙需要支持接收播放补丁 1、device/rockchip/common/overlay/overlay/packages/apps/Blue…...
玩机进阶教程-----高通9008线刷XML脚本修改备份 檫除的操作步骤解析
在高通9008官方固件中我们可以看到刷写需要的脚本rawprogram0.xml和辅助脚本patch0.xml,脚本的作用在于将固件内各个分区对应写入手机内。根据分区地址段。然后判断脚本中那些分区不写入。以下步骤将分析emmc字库为例来讲解如何将默认刷入脚本修改为备份 檫除脚本。…...
前端路径问题总结
1.相对路径 不以/开头 以当前资源的所在路径为出发点去找目标资源 语法: ./表示当前资源的路径 ../表示当前资源的上一层路径 缺点:不同位置,相对路径写法不同2.绝对路径 以固定的路径作为出发点作为目标资源,和当前资源所在路径没关系 语法:以/开头,不同的项目中,固定的路径…...
YOLOv8改进 | 低照度检测 | 2024最新改进CPA-Enhancer链式思考网络(适用低照度、图像去雾、雨天、雪天)
一、本文介绍 本文给大家带来的2024.3月份最新改进机制,由CPA-Enhancer: Chain-of-Thought Prompted Adaptive Enhancer for Object Detection under Unknown Degradations论文提出的CPA-Enhancer链式思考网络,CPA-Enhancer通过引入链式思考提示机制,实现了对未知退化条件下…...
python的pip如何升级
升级pip的方法如下: 打开命令行工具。在Windows系统中,可以通过按下WinR键,然后输入"cmd"来打开命令提示符;在Mac或Linux系统中,可以直接打开终端。检查当前pip版本。在终端或命令行中输入以下命令&#…...
Collection与数据结构 Stack与Queue(一): 栈与Stack
1. 栈 1.1 概念 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈&…...
内部类(来自类和对象的补充)
❤️❤️前言~🥳🎉🎉🎉 hellohello~,大家好💕💕,这里是E绵绵呀✋✋ ,如果觉得这篇文章还不错的话还请点赞❤️❤️收藏💞 💞 关注💥&a…...
Android 高德地图
1.获取Key 进入高德开放平台控制台,创建一个新应用。在创建的应用上点击"添加key"按钮,在弹出的对话框中,依次输入key名称,选择服务平台为“Android平台”,输入发布版安全码 SHA1、以及 Package。 获取 S…...
代码随想录|Day31|贪心06|738.单调递增的数字
738.单调递增的数字 思路: 1. 从右向左遍历 从字符串的最后一位向前遍历,即从低位到高位进行检查。这是因为当我们修改某一位数字时,可能会影响到更低位的数字。 2. 检查并修改数字 在遍历过程中,如果发现当前位数字小于其前一位&…...
机械制造学习笔记
一、切削加工、切削运动的基本概念及刀具切削过程 切削加工: 定义:切削加工是利用切削刀具对工件进行切削,以去除多余材料并得到所需形状和尺寸的加工方法之一。应用:广泛应用于金属加工、木材加工、塑料加工等领域,是…...
Golang | Leetcode Golang题解之第3题无重复字符的最长子串
题目: 题解: func lengthOfLongestSubstring(s string) int {// 哈希集合,记录每个字符是否出现过m : map[byte]int{}n : len(s)// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动r…...
SWM341系列应用(上位机应用)
SWM341系列之上位机应用 1、分级图像和PNG、JPG的应用 现象:客户使用SWM34SVET6HMI_0.4.1版本上位机进行UI界面布局,反馈在模拟运行时(PC端)流畅,在Demo平台(设备端)运行卡顿。 分析及解决&…...
【软件工程】详细设计(一)
1. 引言 1.1 编写目的 该文档的目的是描述《学生成绩管理系统》项目的详细设计,其主要内容包括: 系统功能简介 系统详细设计简述 各个模块的实现逻辑 最小模块组件的伪代码 本文档的预期的读者是: 开发人员 项目管理人员 测试人员 …...
【AIGC】如何在Windows/Linux上部署stable diffusion
文章目录 整体安装步骤windows10安装stable diffusion环境要求安装步骤注意事项参考博客其他事项安装显卡驱动安装cuda卸载cuda安装对应版本pytorch安装git上的python包Q&A linux安装stable diffusion安装anaconda安装cudagit 加速配置虚拟环境挂载oss(optional…...
基于java实现的弹幕视频网站
开发语言:Java 框架:ssm 技术:JSP JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7(一定要5.7版本) 数据库工具:Navicat11 开发软件:eclipse/myeclip…...
网站建设杭州滨江/产品推广网站
这是一个所有做前端都会遇到的问题;布局是这样的,有一个宽高100px背景为红的div,默认是display:none 隐藏状态;给两个a标签绑定的同一个click事件,改变div的display为block;让其显示;…...
如何做视频网站技术/网店运营推广方案
1.微服务 微服务是一种架构风格,一个大型复杂软件应用由一个或多个微服务组成。系统中的各个微服务可被独立部署,各个微服务之间是松耦合的。每个微服务仅关注于完成一件任务并很好地完成该任务。在所有情况下,每个任务代表着一个小的业务能力…...
网站开发项目进度完成表/代发百度关键词排名
题目 最近比较懒,题目描述都直接截图了。 题目大意 给你一棵树,还有树上的几条路径,一条路径上的点到路径上其它任意点的代价为111。然后是一堆询问,问从一个点到另一个点的最小代价。 思路 一开始做这题时,就自然地…...
syntax highlighter for wordpress/黑帽seo教程
毫无PS痕迹 你的第一本Photoshop书 目录 《毫无PS痕迹-你的本Photoshop书》全书分为四大部分: 第1、2章讲解色彩和图像的原理与基础知识要点。 第3至11章全面讲解了使用Photoshop进行各种设计创作的方法与技巧。这包括色彩调整工具的使用、极其重要的选区、蒙版与图…...
网站建设 佛山/阿里云自助建站
刚解决了一个小问题,在此记录一下。 测试服务器上的mysql,当我在本地使用工具去连接它的时候,报错:Lost connection to MySQL server at reading initial communication packet 我首先想到的是要在服务器上给所有IP授权…...
自己做网站挣钱不/360优化大师下载
最近写个http客户端的小程序,由于http是基于tcp的无消息边界保护的协议,所以接受时必须要确定接受数据的数量才能完整接收数据。传统的方式,只要先接收到Content-Length就可以通过这个长度接受消息体部分了。而transfer-encoding:chunked的引…...