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使用未标记的文本进行预训练,并针对有监督的下游任务进行微调。 但上述两种策略…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
