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

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&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target&#xff0c;返回 [-1, -1]。 你必须设计…...

算法刷题框架

前言&#xff1a;最近积累了一些算法题量&#xff0c;正在刷东神的算法笔记&#xff0c;监督自己记录下读后启发&#xff0c;顺便帮助道友们阅读 数据结构 这一部分老生常谈&#xff0c;数据的存储方式只有顺序存储和链式存储。 最基本的数组和链表对应这两者&#xff0c;栈…...

跟着cherno手搓游戏引擎【24】开启2D引擎前的项目总结(包括前置知识汇总)

前置技术&#xff1a; c动态链接和静态链接&#xff1a; 隐藏的细节&#xff1a;编译与链接_哔哩哔哩_bilibili 【底层】动态链接库(dll)是如何工作的&#xff1f;_哔哩哔哩_bilibili 预编译&#xff0c;编译&#xff0c;汇编&#xff0c;链接 预编译头文件&#xff1a; 为…...

石子合并+环形石子合并+能量项链+凸多边形的划分——区间DP

一、石子合并 (经典例题) 设有 N 堆石子排成一排&#xff0c;其编号为 1,2,3,…,N。 每堆石子有一定的质量&#xff0c;可以用一个整数来描述&#xff0c;现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆&#xff0c;合并的代价为这两堆石子的质量之和&#xff0c;…...

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": {"…...

网络安全产品之认识蜜罐

文章目录 一、什么是蜜罐二、蜜罐的主要类型三、蜜罐的主要功能四、蜜罐的主要组成及核心技术五、蜜罐的优缺点六、蜜罐如何与其他安全工具协同工作&#xff1f;七、什么是“蜜网”&#xff1f;与蜜罐的联系和区别是什么&#xff1f; 蜜罐的概念首次由Clifford Stoll在其1988年…...

推荐《架构探险:从零开始写Java Web框架》

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl 春节读了《架构探险&#xff1a;从零开始写Java Web框架》&#xff0c;一本大概10年前的好书。 本书的作者是阿里巴巴架构师黄勇。黄勇对分布式服务架构与大数据技术有深入…...

Go教程-Go语言简介

这篇文章我们来聊聊Go语言。 Go语言发展历史 以下是Go语言发展的几个里程碑节点&#xff1a; Go一开始是Google内部的一个项目&#xff0c;由三位大佬Rob Pike、Robert Griesemer、Ken Thompson早2007年发起。在2009年11月&#xff0c;Go语言正式对外开源。在2010年&#xf…...

React + SpringBoot + Minio实现文件的预览

思路&#xff1a;后端提供接口&#xff0c;从minio获取文件的预览链接&#xff0c;返回给前端&#xff0c;前端使用组件进行渲染展示 这里我从minio获取文件预览地址用到了一个最近刚开源的项目&#xff0c;挺好用的&#xff0c;大伙可以试试&#xff0c;用法也很简单 官网&am…...

心法利器[107] onnx和tensorRT的bert加速方案记录

心法利器 本栏目主要和大家一起讨论近期自己学习的心得和体会&#xff0c;与大家一起成长。具体介绍&#xff1a;仓颉专项&#xff1a;飞机大炮我都会&#xff0c;利器心法我还有。 2023年新一版的文章合集已经发布&#xff0c;获取方式看这里&#xff1a;又添十万字-CS的陋室2…...

AcWing 122 糖果传递(贪心)

[题目概述] 有 n 个小朋友坐成一圈&#xff0c;每人有 a[i] 个糖果。 每人只能给左右两人传递糖果。 每人每次传递一个糖果代价为 1。 求使所有人获得均等糖果的最小代价。 输入格式 第一行输入一个正整数 n&#xff0c;表示小朋友的个数。 接下来 n 行&#xff0c;每行一个…...

unity的重中之重:组件

检查器&#xff08;Hierarchy&#xff09;面板中的所有东西都是组件。日后多数工作都是和组件打交道&#xff0c;包括调参、自定义脚本组件。 文章目录 12 游戏的灵魂&#xff0c;脚本组件13 玩转脚本组件14 尽职的一生&#xff0c;了解组件的生命周期15 不能插队&#xff01;…...

Linux释放内存

free -m是Linux上查看内存的指令&#xff0c;其中-m是以兆&#xff08;MB&#xff09;为单位&#xff0c;如果不加则以KB为单位。 如下图表示&#xff0c;&#xff08;total&#xff09;总物理内存是809MB&#xff0c;&#xff08;used&#xff09;已使用167MB&#xff0c;&…...

Python算法题集_翻转二叉树

Python算法题集_翻转二叉树 题226&#xff1a;翻转二叉树1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【DFS递归】2) 改进版一【BFS迭代&#xff0c;节点循环】3) 改进版二【BFS迭代&#xff0c;列表循环】 4. 最优算法 本文为Python算法题集…...

Git快速掌握,通俗易懂

Git分布式版本控制工具 介绍 Git是一个开源的分布式版本控制系统&#xff0c;用于敏捷高效地处理任何或小或大的项目。Git是由Linus Torvalds为了帮助管理Linux内核开发而开发的一个开放源码的版本控制软件。Git可以帮助开发者们管理代码的版本&#xff0c;避免代码冲突&#…...

PHP毕业设计图片分享网站76t17

图片分享网站主要是为了提高工作人员的工作效率和更方便快捷的满足用户&#xff0c;更好存储所有数据信息及快速方便的检索功能&#xff0c;对系统的各个模块是通过许多今天的发达系统做出合理的分析来确定考虑用户的可操作性&#xff0c;遵循开发的系统优化的原则&#xff0c;…...

代码随想录 Leetcode45. 跳跃游戏 II

题目&#xff1a; 代码(首刷看解析 2024年2月15日&#xff09;&#xff1a; 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使用基于上下文的预训练词嵌入拼接特定于任务的架构&#xff1b;基于微调的方法如GPT使用未标记的文本进行预训练&#xff0c;并针对有监督的下游任务进行微调。 但上述两种策略…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...