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

力扣算法题:34、在排序数组中查找元素的第一个和最后一个位置.java版

版本说明

当前版本号[20230930]。

版本修改说明
20230930初版

34.在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 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

思路

可以点击此篇博客看二分查找算法相关的图解:究竟是什么样的讲解二分查找算法的博客让我写了三小时???

​ 首先,我们可以用二分查找找到目标值 target 在数组中的任意一个位置 mid。若数组中不存在目标值,二分查找会返回不重复的插入位置,我们可以将开始位置和结束位置都设为 -1

​ 接下来,我们可以分别向左边和右边进行二分查找,以找到目标值在数组中的开始位置和结束位置。

​ 向左边查找时,我们不断将右边界设为 mid-1,直到找到排在 mid 前面的目标值或者边界越界。若找到目标值,我们将开始位置设为此位置,否则开始位置将保持为初始值 -1

​ 向右边查找时,我们不断将左边界设为 mid+1,直到找到排在 mid 后面的目标值或者边界越界。若找到目标值,我们将结束位置设为此位置,否则结束位置将保持为初始值 -1

​ 最后,我们返回开始位置和结束位置即可。

返回的新数组左边的值是原先数组最左边的目标值:所以使用左寻找方法要再 j = m - 1; 确保这个值是最左边的

右边的值是原先数组最右边的目标值:所以使用左寻找方法要再 i = m + 1; 确保这个值是最右边的

代码

class Solution
{public int[] searchRange(int[] a , int target) {int k = left(a , target);if(k == -1){return new int[]{-1,-1};}else{return new int[]{k , right(a, target)};}}public int left(int[] a , int target){int i = 0;int j = a.length - 1 ;int candidate = -1 ; //待定值while (i <= j){int m = (i+j) >>> 1;if(target < a[m]){j = m - 1;}else if(a[m] < target){i = m + 1;}else{candidate = m;j = m - 1;   //继续向左走}}return candidate;}public int right(int[] a , int target){int i = 0;int j = a.length - 1 ;int candidate = -1 ; //待定值while (i <= j){int m = (i+j) >>> 1;if(target < a[m]){j = m - 1;}else if(a[m] < target){i = m + 1;}else{candidate = m;i = m + 1;  //继续向右走}}return candidate;}
}

总结

​ 这段代码目的是查找一个按非递减顺序排列的整数数组中某个目标值的起始位置和结束位置。

​ 该函数采用了二分查找的算法思想,实现了一个函数 searchRange,用来实现时间复杂度为 O(log n) 的查找效率。具体来说,它通过调用 left 函数找到目标值在数组中的起始位置,然后再调用 right 函数找到目标值在数组中的结束位置。

left 函数是一个二分查找算法的实现,它将数组分为两部分,通过不断更新起始位置和结束位置的指针,来逼近目标值的起始位置。每次循环中,它先计算中间位置 m,然后比较目标值与 a[m] 的大小,根据结果更新指针。如果目标值等于 a[m],则更新一个候选位置 candidatem,然后继续向左走以找到起始位置。最后,返回候选位置作为结果。

right 函数同样是一个二分查找算法的实现,它与 left 函数类似,只是在查找目标值的结束位置时,向右走以逼近结束位置。

​ 总体而言,这段代码通过两次二分查找操作,高效地找到了目标值在数组中的起始位置和结束位置。它的时间复杂度为 O(log n),适用于大规模数据的查找。使用二分查找的思想,可以快速定位目标值并获取起始位置和结束位置的结果。

http://www.lryc.cn/news/179987.html

相关文章:

  • [网鼎杯 2020 朱雀组]Nmap
  • 【Leetcode】166.分数到小数
  • 2023-10-01 LeetCode每日一题(买卖股票的最佳时机)
  • 解决 ARouter 无法生成路由表,Toast提示 找不到目标路由
  • 排序算法之【希尔排序】
  • 防火墙基础之H3C防火墙分支与分支之间双向地址转换
  • 【考研数学】概率论与数理统计 —— 第三章 | 二维随机变量及其分布(1,二维连续型和离散型随机变量基本概念与性质)
  • cesium 雷达扫描 (波纹线性雷达扫描效果)
  • SLAM从入门到精通(tf的使用)
  • python代码混淆与代码打包
  • Codeforces Round 899 (Div. 2)
  • 【 SuperPoint 】图像特征提取上的对比实验
  • Chrome获取RequestId
  • cesium 雷达扫描 (线行扩散效果)
  • 【React】React组件生命周期以及触发顺序(部分与vue做比较)
  • 【C++】多线程的学习笔记——白话文版(bushi
  • 图像处理: ImageKit.NET 3.0.10704 Crack
  • K8S内容分发网络之集群,nginx,负载均衡,防火墙
  • 不愧是疑问解决神器!你强任你强
  • 盛最多水的容器 接雨水【基础算法精讲 02】
  • WordPress主题开发( 十二)之—— 主题的functions.php
  • 代码的工厂模式
  • UE5.1编辑器拓展【一、脚本化资产行为,通知,弹窗,高效复制多个同样的资产】
  • mac openssl 版本到底怎么回事 已解决
  • AWS】在EC2上创建root用户,并使用root用户登录
  • 9月24日回顾
  • Spring注册Bean系列--方法1:@Component
  • 防火墙基础之H3C防火墙和三层交换机链路聚合的配置
  • 管理类联考——数学——汇总篇——知识点突破——算数——记忆
  • leetCode 455.分发饼干 贪心算法