当前位置:   article > 正文

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

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

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


给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置如果数组中不存在目标值 target,返回 [-1, -1]。

时间复杂度要求: O ( log ⁡ n ) O(\log n) O(logn)

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
  • 1
  • 2

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
  • 1
  • 2

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]
  • 1
  • 2

示例 4:

输入:nums =[5,7,7,8,8,10], target = 4或11
输出:[-1,-1]
  • 1
  • 2

简单分析下:本题数组有序但元素未必唯一了,因此可能找到多个target,我们需要做的就是确定这些连续target的左边界和右边界位置。依然是通过二分查找来搜索,只不过标准二分是mid找到一个target就直接return,此时while循环没有退出。而这里找边界,则不能找到一个target就return,必须通过left,right汇聚然后while循环退出,相应的left/right就对应左/右边界。左右边界的查找还是自己举例最为清晰。


解法一


1、二分查找target左右边界


二分查找左边界:找不到返回-1
  1. nums[mid] == target则right = mid - 1继续往左逼近,其他与二分查找没有区别
  2. 举例可知,能找到target的情况下,跳出循环时nums[left]=target 是其左边界返回left即可
    • 换个角度理解为什么left是最终的左边界而不是right:在能找到target也就是存在nums[mid]=target的情况时,right = mid-1,那么while退出时必然right不可能是target了【直接举个例子更清晰】
  3. 找不到target的情况下,跳出循环时nums[left] != target,令left = -1返回

二分查找右边界:找不到返回-1
  1. nums[mid] == target则left = mid + 1继续往左逼近,其他不变

  2. 举例可知,能找到target的情况下,跳出循环nums[right]=target是其右边界返回right即可

  3. 找不到target的情况下,nums[right] != target,令right = -1返回


nums空时的越界问题

注意:nums为空集时,初始left = 0, right = 1,本来标准二分不会越界的,但是这里找边界添加了if nums[right/left]==target判断,那就会left/right = 0/-1,会越界,需单独处理


2、返回情况


  1. target能被找到:左边界/右边界最终下标,return [left_border, right_border]
  2. target找不到,return [-1, -1]
    • 2.1 target在数组范围内:左边界/右边界最终下标对应不到target,此时都被赋值为-1了!!
    • 2.2 target不在数组范围内:判断下数组max和min即可
    • 2.3 数组是空集

3、python实现1【推荐】


时间复杂度: 2 ∗ O ( log ⁡ N ) 2*O(\log N) 2O(logN),调用两次二分查找

执行用时:36 ms, 在所有 Python3 提交中击败了75.41% 的用户
内存消耗:15.9 MB, 在所有 Python3 提交中击败了86.09% 的用户

参考题解

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
		# 返回情况2.2 2.3
        if not nums or nums[0] > target or nums[-1] < target:
            return [-1, -1]
        else:    # 返回情况 1, 2.1    
            left_border = self.binary_search_left_border(nums, target, 0, len(nums)-1)
            right_border = self. binary_search_right_border(nums, target, 0, len(nums)-1)
            return [left_border, right_border]
        

    def binary_search_left_border(self, nums, target, left, right) -> int:
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                right = mid - 1 # 向左逼近
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        if nums[left] == target:
            return left
        else:
            return -1

    def binary_search_right_border(self, nums, target, left, right) -> int:
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                left = mid + 1 # 向右逼近
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        if nums[right] == target:
            return right
        else:
            return -1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

4、python实现2

这里的分类和二分搜索与上面有些不同,个人觉得没有上面写的清楚,可以做个参考。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # border都差了一位
        left_border = self.binary_search_border_left(nums, 0, len(nums)-1, target) 
        right_border = self.binary_search_border_right(nums, 0, len(nums)-1, target) 
        # target在数组范围之外,注意是or!!
        if left_border == -2 or right_border == -2:
            return [-1, -1]
        # 能找到target(一个或连续多个)需满足 (left - right) >= 0
        elif ((right_border-1)-(left_border+1)) >= 0:
            return [left_border+1, right_border-1]
        else: # target 在数组范围之内,但是不在数组内
            return [-1, -1]
        

    def binary_search_border_left(self, nums, low, high, target):
        left_border = -2
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] >= target:
                high = mid -1
                left_border = high
            else:
                low = mid + 1
        return left_border


    def binary_search_border_right(self, nums, low, high, target):
        right_border = -2
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] <= target:
                low = mid + 1
                right_border = low
            else:
                high = mid - 1
        return right_border
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/436777
推荐阅读
相关标签
  

闽ICP备14008679号