范湖网站建设哪家便宜,脚本语言在网站开发中,便民平台推广怎么做,html5 电商网站布局版本说明
当前版本号[20230930]。
版本修改说明20230930初版
34.在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的…版本说明
当前版本号[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] 109nums 是一个非递减数组-109 target 109
思路
可以点击此篇博客看二分查找算法相关的图解究竟是什么样的讲解二分查找算法的博客让我写了三小时
首先我们可以用二分查找找到目标值 target 在数组中的任意一个位置 mid。若数组中不存在目标值二分查找会返回不重复的插入位置我们可以将开始位置和结束位置都设为 -1。
接下来我们可以分别向左边和右边进行二分查找以找到目标值在数组中的开始位置和结束位置。
向左边查找时我们不断将右边界设为 mid-1直到找到排在 mid 前面的目标值或者边界越界。若找到目标值我们将开始位置设为此位置否则开始位置将保持为初始值 -1。
向右边查找时我们不断将左边界设为 mid1直到找到排在 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 (ij) 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 (ij) 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]则更新一个候选位置 candidate 为 m然后继续向左走以找到起始位置。最后返回候选位置作为结果。
right 函数同样是一个二分查找算法的实现它与 left 函数类似只是在查找目标值的结束位置时向右走以逼近结束位置。
总体而言这段代码通过两次二分查找操作高效地找到了目标值在数组中的起始位置和结束位置。它的时间复杂度为 O(log n)适用于大规模数据的查找。使用二分查找的思想可以快速定位目标值并获取起始位置和结束位置的结果。
