leetcode(二分查找)34.在排序数组中查找元素的第一个和最后一个位置(C++详细解释)DAY11
文章目录
- 1.题目
- 示例
- 提示
- 2.解答思路
- 3.实现代码
- 结果
- 4.总结
1.题目
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例

提示

2.解答思路
提取信息:
1.时间复杂度必须为O(logn)
2.没查找到时返回{-1,-1}查找到就返回下标
本题难点:二分查找的实现:
查找第一个小于target和第一个大于target的值
3.实现代码
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int>ans;int n=nums.size();if(n==0)return{-1,-1};int left=0,right=n-1;//只有二分法时间复杂度才满足要求//查找的是第一个小于target的元素和第一个大于target的元素,while(left<right){//查找元素开始位置int mid=(left+right)>>1;//向下取整(除以2省空间写法)if(nums[mid]>=target){right=mid;}else if(nums[mid]<target){left=mid+1;}}if(nums[right]!=target)return{-1,-1};//查找失败ans.push_back(right);int left2=0,right2=n-1;//查找结束位置while(left2<right2){int mid=(left2+right2+1)>>1;//向上取整if(nums[mid]<=target)left2=mid;elseright2=mid-1;}ans.push_back(right2);return ans;}
};
结果

用时约两个小时+,目前的解法性能不是很好,有时间继续改进。
4.总结
本来以为挺简单的一道题,题不可貌相。
限定的时间复杂度决定了只能使用二分查找,二分查找的细节还需要好好整理一下,再完善该题。
自信,坚持,upup~
相关文章:
leetcode(二分查找)34.在排序数组中查找元素的第一个和最后一个位置(C++详细解释)DAY11
文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计…...
算法刷题框架
前言:最近积累了一些算法题量,正在刷东神的算法笔记,监督自己记录下读后启发,顺便帮助道友们阅读 数据结构 这一部分老生常谈,数据的存储方式只有顺序存储和链式存储。 最基本的数组和链表对应这两者,栈…...
跟着cherno手搓游戏引擎【24】开启2D引擎前的项目总结(包括前置知识汇总)
前置技术: c动态链接和静态链接: 隐藏的细节:编译与链接_哔哩哔哩_bilibili 【底层】动态链接库(dll)是如何工作的?_哔哩哔哩_bilibili 预编译,编译,汇编,链接 预编译头文件: 为…...
石子合并+环形石子合并+能量项链+凸多边形的划分——区间DP
一、石子合并 (经典例题) 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,…...
IMX6ULL移植U-Boot 2022.04
目录 目录 1.编译环境以及uboot版本 2.默认编译测试 3.uboot中新增自己的开发板 3.编译测试 4.烧录测试 5.patch文件 1.编译环境以及uboot版本 宿主机Debian12u-boot版本lf_v2022.04 ; git 连接GitHub - nxp-imx/uboot-imx: i.MX U-Boot交叉编译工具gcc-arm-10.3-2021.0…...
ES实战-高级聚合
多桶型聚合 1.词条聚合–terms 2.范围聚合–range 3,直方图聚合–histogram/日期直方图 4.嵌套聚合 5.地理距离聚合 include(包含)exclude(不包含) GET /get-together/_search?pretty {"size": 0,"aggs": {"tags": {"terms": {"…...
网络安全产品之认识蜜罐
文章目录 一、什么是蜜罐二、蜜罐的主要类型三、蜜罐的主要功能四、蜜罐的主要组成及核心技术五、蜜罐的优缺点六、蜜罐如何与其他安全工具协同工作?七、什么是“蜜网”?与蜜罐的联系和区别是什么? 蜜罐的概念首次由Clifford Stoll在其1988年…...
推荐《架构探险:从零开始写Java Web框架》
版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl 春节读了《架构探险:从零开始写Java Web框架》,一本大概10年前的好书。 本书的作者是阿里巴巴架构师黄勇。黄勇对分布式服务架构与大数据技术有深入…...
Go教程-Go语言简介
这篇文章我们来聊聊Go语言。 Go语言发展历史 以下是Go语言发展的几个里程碑节点: Go一开始是Google内部的一个项目,由三位大佬Rob Pike、Robert Griesemer、Ken Thompson早2007年发起。在2009年11月,Go语言正式对外开源。在2010年…...
React + SpringBoot + Minio实现文件的预览
思路:后端提供接口,从minio获取文件的预览链接,返回给前端,前端使用组件进行渲染展示 这里我从minio获取文件预览地址用到了一个最近刚开源的项目,挺好用的,大伙可以试试,用法也很简单 官网&am…...
心法利器[107] onnx和tensorRT的bert加速方案记录
心法利器 本栏目主要和大家一起讨论近期自己学习的心得和体会,与大家一起成长。具体介绍:仓颉专项:飞机大炮我都会,利器心法我还有。 2023年新一版的文章合集已经发布,获取方式看这里:又添十万字-CS的陋室2…...
AcWing 122 糖果传递(贪心)
[题目概述] 有 n 个小朋友坐成一圈,每人有 a[i] 个糖果。 每人只能给左右两人传递糖果。 每人每次传递一个糖果代价为 1。 求使所有人获得均等糖果的最小代价。 输入格式 第一行输入一个正整数 n,表示小朋友的个数。 接下来 n 行,每行一个…...
unity的重中之重:组件
检查器(Hierarchy)面板中的所有东西都是组件。日后多数工作都是和组件打交道,包括调参、自定义脚本组件。 文章目录 12 游戏的灵魂,脚本组件13 玩转脚本组件14 尽职的一生,了解组件的生命周期15 不能插队!…...
Linux释放内存
free -m是Linux上查看内存的指令,其中-m是以兆(MB)为单位,如果不加则以KB为单位。 如下图表示,(total)总物理内存是809MB,(used)已使用167MB,&…...
Python算法题集_翻转二叉树
Python算法题集_翻转二叉树 题226:翻转二叉树1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【DFS递归】2) 改进版一【BFS迭代,节点循环】3) 改进版二【BFS迭代,列表循环】 4. 最优算法 本文为Python算法题集…...
Git快速掌握,通俗易懂
Git分布式版本控制工具 介绍 Git是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目。Git是由Linus Torvalds为了帮助管理Linux内核开发而开发的一个开放源码的版本控制软件。Git可以帮助开发者们管理代码的版本,避免代码冲突&#…...
PHP毕业设计图片分享网站76t17
图片分享网站主要是为了提高工作人员的工作效率和更方便快捷的满足用户,更好存储所有数据信息及快速方便的检索功能,对系统的各个模块是通过许多今天的发达系统做出合理的分析来确定考虑用户的可操作性,遵循开发的系统优化的原则,…...
代码随想录 Leetcode45. 跳跃游戏 II
题目: 代码(首刷看解析 2024年2月15日): class Solution { public:int jump(vector<int>& nums) {if (nums.size() 1) return 0;int res 0;int curDistance 0;int nextDistance 0;for (int i 0; i < nums.size(); i) {nex…...
【C语言】socketpair 的系统调用
一、 Linux 内核 4.19socketpair 的系统调用 SYSCALL_DEFINE4(socketpair, int, family, int, type, int, protocol,int __user *, usockvec) {return __sys_socketpair(family, type, protocol, usockvec); } 这段代码定义了一个名为 socketpair 的系统调用。系统调用是操作…...
【论文精读】BERT
摘要 以往的预训练语言表示应用于下游任务时的策略有基于特征和微调两种。其中基于特征的方法如ELMo使用基于上下文的预训练词嵌入拼接特定于任务的架构;基于微调的方法如GPT使用未标记的文本进行预训练,并针对有监督的下游任务进行微调。 但上述两种策略…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
