首页 > 编程语言 >python 在排序数组中查找元素的第一个和最后一个位置 多种解法

python 在排序数组中查找元素的第一个和最后一个位置 多种解法

时间:2024-01-17 10:35:36浏览次数:31  
标签:right target nums python mid bisect 查找 解法 left

  1. 二分查找:基于二分查找的算法可以在 O(log n) 的时间复杂度内解决该问题。具体实现方式是,先使用二分查找找到该元素的位置,然后向左和向右扩展,直到找到第一个和最后一个位置。代码如下:
def searchRange(nums, target):
    def binarySearch(nums, target, lower):
        left, right = 0, len(nums) - 1
        ans = len(nums)
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target or (lower and nums[mid] >= target):
                right = mid - 1
                ans = mid
            else:
                left = mid + 1
        return ans

    leftIdx = binarySearch(nums, target, True)
    rightIdx = binarySearch(nums, target, False) - 1

    if leftIdx <= rightIdx and rightIdx < len(nums) and nums[leftIdx] == target and nums[rightIdx] == target:
        return [leftIdx, rightIdx]

    return [-1, -1]
  1. 线性扫描:线性扫描的思路是从左到右遍历数组,记录第一次出现目标值的位置,然后继续遍历数组,直到找到最后一次出现目标值的位置,代码如下:
def searchRange(nums, target):
    first, last = -1, -1
    for i in range(len(nums)):
        if nums[i] == target:
            if first == -1:
                first = i
            last = i
    return [first, last]
  1. 使用 Python 内置函数:Python 中有内置函数 bisect_left 和 bisect_right 可以帮助我们实现二分查找。代码如下:
import bisect

def searchRange(nums, target):
    left = bisect.bisect_left(nums, target)
    right = bisect.bisect_right(nums, target) - 1
    if left <= right and nums[left] == target and nums[right] == target:
        return [left, right]
    return [-1, -1]

标签:right,target,nums,python,mid,bisect,查找,解法,left
From: https://blog.51cto.com/lzning/9286779

相关文章