题目描述:
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
思路1:
1、二分法先找到右边界;
1、设定左右指针left = 0和right=len-1,找到中间数num[min]
2、比较目标值与num[min]的大小,大于目标值则修改右指针right = mid - 1;
3、小于目标值则修改左指针 left = mid + 1;
4、等于目标值,则判断是否该指针是最后一个,或者是否下一个数比目标值大,如果都不是,如是,则ans[1] = mid;如否,则修改左指针left = mid + 1;
2、二分法再找到左边界;
1、设定左右指针left = 0和right=ans[1],找到中间数num[min]
2、比较目标值与num[min]的大小,大于目标值则修改右指针right = mid - 1;
3、小于目标值则修改左指针 left = mid + 1;
4、等于目标值,则判断是否该指针是第一个,或者是否前一个数比目标值小,如是,则ans[0] = mid;如否,则修改左指针right = mid - 1;
3、最终返回结果ans;
Java解法:
class Solution {
public int[] searchRange(int[] nums, int target) {
int len = nums.length;
if(len ==0 || nums[0] > target || nums[len - 1] < target){
return new int[]{-1, -1};
}
int left = 0;
int right = len - 1;
int[] ans = new int[]{-1, -1};
while(left <= right)
{
int mid = (left + right) / 2;
if (nums[mid] > target)
{
right = mid - 1;
}else if(nums[mid] < target)
{
left = mid + 1;
}else {
if (mid == len - 1 || nums[mid + 1] > target)
{
ans[1] = mid;
break;
}else
{
left = mid + 1;
}
}
}
left = 0;
right = ans[1];
while(left <= right)
{
int mid = (left + right) / 2;
if (nums[mid] > target)
{
right = mid - 1;
}else if(nums[mid] < target)
{
left = mid + 1;
}else {
if (mid == 0 || nums[mid - 1] < target)
{
ans[0] = mid;
break;
}else
{
right = mid - 1;
}
}
}
return ans;
}
}
python3解法:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
网友评论