leetcode34-- Find First and Last Position of Element in Sorted Array

leetcode34-- Find First and Last Position of Element in Sorted Array

题目

34. Find First and Last Position of Element in Sorted Array
Medium

1199

64

Favorite

Share
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

解法

这个题目的意思是在一个排好序的数组里面(可能会有重复的元素), 然后找出给定的一个数target的它的第一次出现和最后一次出现的index.

我最初想的是先找到这个元素的位置,只要找到一个就行,然后再向前向后计算其两个端点的位置,最终写的比较乱, 不过通过了


class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return [-1, -1]
        if len(nums) == 1 and target==nums[0]:
            return [0,0]
        if len(nums)==1 and target != nums[0]:
            return [-1, -1]
            
        
        start, end = 0, len(nums)-1
        
        
        flag = -1
        while(start+1<end):
            mid = start + (end-start)/2
            
            if nums[mid]==target:
                flag = mid
                break
            elif(nums[mid]>target):
                end = mid
            else:
                start = mid
                
        Start, End = -1,-1
        
        if(flag!=-1):
            # 向前向后找
            temp1 = flag
            temp2 = flag
            while( nums[temp1] == target):
                temp1 -=1
                if temp1<0:
                    break
            while(nums[temp2]==target):
                temp2 += 1
                if temp2>len(nums)-1:
                    break
            
            Start = temp1+1
            End = temp2 -1    
            return [Start, End]
        else:
            if(nums[start] == target):
                flag = start
                temp1 = flag
                temp2 = flag
                while( nums[temp1] == target):
                    temp1 -=1
                    if temp1<0:
                        break
                while(nums[temp2]==target):
                    temp2 += 1
                    if temp2>len(nums)-1:
                        break

                Start = temp1+1
                End = temp2 -1    
                return [Start, End]

                
            elif(nums[end]==target):
                
                flag = end
                temp1 = flag
                temp2 = flag
                while( nums[temp1] == target):
                    temp1 -=1
                    if temp1 <0:
                        break
                while(nums[temp2]==target):
                    temp2 += 1
                    if temp2>len(nums)-1:
                      break

                Start = temp1+1
                End = temp2 -1    
                return [Start, End]
            else:
                return [-1, -1]


不过如果用c++中的’equal_range’的话就比较方便了。


class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto ret = equal_range(nums.begin(), nums.end(), target);
        if(ret.first==ret.second){
            return {-1,-1};
        }
        return {ret.first-nums.begin(), ret.second-nums.begin()-1};
        
    }
};


上面equal_range返回的是[a,b)类型的,所以要右边的要再减去1.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦