Skip to content

034.md

Latest commit

 

History

History
142 lines (119 loc) · 4.2 KB

034.md

File metadata and controls

142 lines (119 loc) · 4.2 KB

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

难度: Medium

刷题内容

原题连接

内容描述

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]

解题方案

思路 1 - 时间复杂度: O(lgN) - 空间复杂度: O(1)

二分法，先找target出现的左边界，判断是否有target后再判断右边界

  • 找左边界：二分，找到一个index
    • 该index对应的值为target
    • 并且它左边index-1对应的值不是target（如果index为0则不需要判断此条件）
    • 如果存在index就将其append到res中
  • 判断此时res是否为空，如果为空，说明压根不存在target，返回[-1, -1]
  • 找右边界：二分，找到一个index（但是此时用于二分循环的l可以保持不变，r重置为len(nums)-1，这样程序可以更快一些）
    • 该index对应的值为target
    • 并且它右边index+1对应的值不是target（如果index为len(nums)-1则不需要判断此条件）
    • 如果存在index就将其append到res中

AC 代码

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums or len(nums) == 0: 
            return [-1, -1]

        res = []
        l, r = 0, len(nums)-1
        # search for left bound
        while l <= r:
            mid = l + ((r - l) >> 2)
            if nums[mid] == target and (mid == 0 or nums[mid-1] != target):
                res.append(mid)
                break
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        if not res:
            return [-1, -1]
        
        # search for right bound
        r = len(nums)-1
        while l <= r:
            mid = l + ((r - l) >> 2)
            if nums[mid] == target and (mid == len(nums)-1 or nums[mid+1] != target):
                res.append(mid)
                break
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1 
        # 这里直接返回res是因为前面如果判断左边界没返回的话就说明我们判断右边界的时候一定会append元素
        return res

思路 2 - 时间复杂度: O(lgN) - 空间复杂度: O(1)

跟第35题一样的思路，先找到第一个大于等于target的值的index，再找到最后一个小于等于target的值的index，然后做一些边界判断，就可以了。

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums or len(nums) == 0: 
            return [-1, -1]
        res = []
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + ((r-l) >> 1)
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        if l <= len(nums) - 1:
            if nums[l] != target:
                return [-1, -1]
            else:
                res.append(l)
        else:
            if nums[l-1] != target:
                return [-1, -1]
            else:
                res.append(l-1)
            
        r = len(nums) - 1
        while l <= r:
            mid = l + ((r-l) >> 1)
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        if r >= 0:
            if nums[r] != target:
                res.append(-1)
            else:
                res.append(r) 
        else:
            if nums[r+1] != target:
                res.append(-1)
            else:
                res.append(r+1)
        return res