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

2021年5月15日 260点热度 2人点赞 0条评论

题目描述

给定一个按照升序排列的整数数组 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 \leq nums.length \leq 10^5$
  • $-10^9 \leq nums[i] \leq 10^9$
  • $nums \quad 是一个非递减数组$
  • $-10^9 \leq target \leq 10^9$

解题思路

这道题我一开始的思路是用二分法去求得一个target对应的下标index,然后再从index开始向左向右去扫描得到leftright

示例代码如下:

int binarySearch(vector<int>& nums,int target,int left,int right)
{
    int mid=(left+right)/2;
    if(nums[mid]==target) return mid;
    if(left>right) return -1;
    if(nums[mid]<target)
    {
        return binarySearch(nums,target,mid+1,right);
    }
    else{
        return binarySearch(nums,target,left,mid-1);
    }
}

vector<int> searchRange(vector<int>& nums, int target)
{
    if(nums.empty()) return {-1,-1};
    int index=binarySearch(nums,target,0,nums.size()-1);
    if(index==-1) return {-1,-1};
    int left=index;
    int right=index;

    while((right+1<nums.size())&&(nums[right]==nums[right+1]))
    {
        right++;
    }

    while((left>0)&&(nums[left]==nums[left-1]))
    {
        left--;
    }
    return {left,right};
}

但是这样子的最好时间复杂度为$O(logn)$,最坏时间复杂度为$O(n)$,不满足条件。

如果要达到$O(logn)$的时间复杂度,那么就要用二分法分别求出下界left和上界right

其中的关键主要是每一次迭代过程中leftright的更新,如果想求上界,那么只有当nums[mid]>target时才更新rightmid-1;如果想求下界,那么就要在nums[mid]>=target时就更新rightmid-1。对left的更新也类似。但是,按照这种方法更新得到的上界会大1,需要减掉。

具体细节见代码:

int binarySearch(vector<int>& nums,int target,bool findLeft)
{
    int left=0;
    int right=nums.size()-1;
    int ans=nums.size();
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(nums[mid]>target||(findLeft&&nums[mid]>=target))
        {
            right=mid-1;
            ans=mid;
        }
        else{
            left=mid+1;
        }

    }
    return ans;
}

vector<int> searchRange(vector<int>& nums, int target)
{
    if(nums.empty()) return {-1,-1};
    int left=binarySearch(nums,target,true);
    int right=binarySearch(nums,target,false)-1;
    //cout<<left<<" "<<right<<endl;
    if(left<nums.size()&&right<nums.size()&&nums[left]==nums[right]) return {left,right};
    return {-1,-1};

}

时间复杂度为:$O(logn)$

空间复杂度为:$O(1)$

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论