【刷题记录】34. 在排序数组中查找元素的第一个和最后一个位置

简介: 【刷题记录】34. 在排序数组中查找元素的第一个和最后一个位置

一、题目描述


来源:力扣(LeetCode)


给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:


  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?


示例 1:


输入:nums = [5,7,7,8,8,10], target = 8

输出:[3,4]


示例 2:


输入:nums = [5,7,7,8,8,10], target = 6

输出:[-1,-1]


示例 3:


输入:nums = [], target = 0

输出:[-1,-1]


提示:


  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109


二丶思路分析


二分查找


这个还是一道二分查找的题目,就不多做解释了,可以参考之前的题目
针对这个道题目


  • 当判断使用nums[mid]>=target 时,找到的是 第一个 位置
  • 当判断使用 nums[mid] <= target时,找到的是 最后一个位置


三、代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1, -1};
        int length = nums.length;
if (length ==0) return ans;
        int l =0, r = length -1;
        // 查找第一个位置
while (l < r) {
            int mid = l + r >> 1;
if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid +1;
            }
        }
        // 不存在 直接返回
if (nums[l] != target) {
            return ans;
        }
        //查找最后一个位置
        ans[0] = l;
        l =0;
        r = length -1;
while (l < r) {
            int mid = l + r +1 >> 1;
if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid -1;
            }
        }
        ans[1] = l;
        return ans;
    }
}


复杂度分析


  • 时间复杂度:
    网络异常,图片无法展示
    |
  • 空间复杂度:
    网络异常,图片无法展示
    |


运行结果


网络异常,图片无法展示
|


总结


这还是一个二分查找的运行,就不再过多的多什么总结了。


这道题目的关键点就是根据什么样的判断条件,可以得到我们想要的第一个目标值或者最后一个目标值,理解了这个就很简单了。


继续加油~~

目录
相关文章
|
自然语言处理 异构计算
ICLR 2024 Poster:精确且高效的大语言模型低比特量化方法 QLLM
【2月更文挑战第24天】ICLR 2024 Poster:精确且高效的大语言模型低比特量化方法 QLLM
341 3
ICLR 2024 Poster:精确且高效的大语言模型低比特量化方法 QLLM
|
小程序 API 索引
uniapp中uview组件库中丰富的Picker 选择器用法
uniapp中uview组件库中丰富的Picker 选择器用法
1883 0
|
存储 运维 监控
阿里云对象存储 OSS 发布全球第一可用性 SLA 背后的技术体系
2020年6月,阿里云对象存储 OSS 通过十年积累的技术红利,将可用性 SLA(Service Level Agreement) 提升 10 倍,做到了全球第一的核心竞争力,是其他的云厂家的 10~20 倍,如下图所示。
1981 0
阿里云对象存储 OSS 发布全球第一可用性 SLA 背后的技术体系
|
运维 负载均衡 Java
认识微服务,认识Spring Cloud
认识微服务,认识Spring Cloud
157 2
|
索引
PyQt5 技术篇-QComboBox下拉框绑定监听事件实例演示
PyQt5 技术篇-QComboBox下拉框绑定监听事件实例演示
1175 0
|
JavaScript Java 测试技术
基于ssm+vue.js+uniapp小程序的学生宿舍设备报修管理系统附带文章和源代码部署视频讲解等
基于ssm+vue.js+uniapp小程序的学生宿舍设备报修管理系统附带文章和源代码部署视频讲解等
100 0
|
算法
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)(上)
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)
70 0
|
域名解析 弹性计算 运维
多账号共享一套ACR方案
一家多业务组织的客户来说往往会有多个云账号,分别部署各个业务线的容器服务。但集团可能想使用一套统一的容器镜像仓库(ACR),就会面临多账号内多个ACK共享一套ACR了。那如何合理规划好ACR实例上的命名空间,打通各个业务ACK集群与ACR的网络,包括如何精细化授权,都是客户需要考虑的。
273 3
多账号共享一套ACR方案
|
前端开发 API PHP
漏刻有时API接口实战开发系列(4):萤石云HTTP接口API开发获取accessToken(php)
漏刻有时API接口实战开发系列(4):萤石云HTTP接口API开发获取accessToken(php)
554 0
|
消息中间件 RocketMQ
rocketMQ 消息重试的问题
将 consumeMessageBatchMaxSize 设置为 大于1 的时候 数据重试会导致 部分数据消费不到的情况
710 0
rocketMQ 消息重试的问题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等