这是我参与11月更文挑战的第10天,活动详情查看:2021最后一次更文挑战
题目
给定一个按照升序排列的整数数组 nums
,和一个目标值 target
。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
进阶:
- 你可以设计并实现时间复杂度为
O(log n)
的算法解决此问题吗?
示例
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
复制代码
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
复制代码
输入: nums = [], target = 0
输出: [-1,-1]
复制代码
提示
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums
是一个非递减数组-10^9 <= target <= 10^9
解题思路
遍历
遍历数组,找到目标值的起始位置,往后搜索找到右边界。
class Solution {
public int[] searchRange(int[] nums, int target) {
for(int i = 0; i < nums.length; ++i){
// 找到目标值起始位置
if(nums[i] == target){
// 往后搜索
int j = i + 1;
while(j < nums.length && nums[j] == target){
++j;
}
// 返回结果
return new int[]{i, j - 1};
}else if(nums[i] > target){
break;
}
}
// 没找到,返回 -1
return new int[]{-1, -1};
}
}
复制代码
- 时间复杂度:
- 空间复杂度:
二分查找
使用遍历搜索,最差的情况需要找到最后一位元素才能找到目标值,效率比较低。
想要在有序的数组中找到目标值,可以采用二分查找来排查,每次可以直接排查掉一半的元素,有效提升查找效率。
步骤:
- 先在数组中找到目标值
target
; - 找到目标值之后,从
mid
指针处,往两边延申搜索; - 找到边界后返回结果;
- 没找到目标值,返回
-1
.
class Solution {
public int[] searchRange(int[] nums, int target) {
// 定义左右边界两个指针
int left = 0, right = nums.length - 1;
// 终止条件,记得是要 小于等于,如果只有小于的话,数组只有单个元素且为目标值,不会进入该循环
while(left <= right){
// 中间点
int mid = left + (right - left) / 2;
// 大于目标值,右边界左移
if(nums[mid] > target){
right = mid - 1;
// 小于目标值,左边界右移
}else if(nums[mid] < target){
left = mid + 1;
}else{
// 等于目标值,从中间点往两边搜索查找边界
left = right = mid;
while(left >= 0 && nums[left] == target){
--left;
}
while(right < nums.length && nums[right] == target){
++right;
}
// 返回区间
return new int[]{left + 1, right - 1};
}
}
// 未找到,返回 -1
return new int[]{-1, -1};
}
}
复制代码
复杂度分析
- 时间复杂度:
- 空间复杂度:
最后
文章有写的不好的地方,请大佬们不吝赐教,错误是最能让人成长的,愿我与大佬间的距离逐渐缩短!
如果觉得文章对你有帮助,请 点赞、收藏、关注、评论 一键四连支持,你的支持就是我创作最大的动力!!!
近期评论