vlambda博客
学习文章列表

示例 1: 输入: [1,3,5,6], 5输出: 2
示例 2:输入: [1,3,5,6], 2输出: 1
示例 3:输入: [1,3,5,6], 7输出: 4
示例 4:输入: [1,3,5,6], 0输出: 0#来源：力扣（LeetCode）#链接：https://leetcode-cn.com/problems/search-insert-position

class Solution: def searchInsert(self, nums: List[int], target: int) -> int: # 空列表情况 if nums==[]: return 0 length = len(nums) # 只有一个数的列表情况 if length<2: if nums[0]>=target: return 0 else: return 1 # 目标值不在列表值范围内情况 if target<=nums[0]: return 0 if target> nums[-1]: return length  # 二分查找法开始 # 定义左右边界位置，最左端和最右端索引 l,r = 0,length-1 # while 循环控制 l 和 r 来缩小范围 while l<r: # 取中点，这里的取值会偏左，比如第 1、2 位取的中点是第 1 位 mid = (l+r)//2 # 如果中点处值为目标，直接返回中点索引 if nums[mid]==target: return mid # 若中点值大于目标，目标在左边部分，此时将右边界变为 mid # 这里不取 mid-1 的原因：取中点是偏左的，是无法取到右边界处的；如果 mid-1 处恰好为目标值，将其定为右边界就会导致中点无法取到该位置，故右边界我们取 mid elif nums[mid]>target: r = mid # 左边界可以跳过 mid 取 mid+1 原因在于，取中点可以取到左边界 else: l = mid+1 # 无论是否存在目标，经历过循环后，l 为目标的位置索引 return l

执行用时 : 40 ms, 在所有 Python3 提交中击败了 79.75% 的用户内存消耗 : 14.4 MB, 在所有 Python3 提交中击败了 7.14% 的用户

示例 1：输入: nums = [4,5,6,7,0,1,2], target = 0输出: 4
示例 2:输入: nums = [4,5,6,7,0,1,2], target = 3输出: -1

class Solution: def search(self, nums: List[int], target: int) -> int: length = len(nums) # 对空列表和只有一个数的列表特殊处理 if length<2: if nums and nums[0]==target: return 0 else: return -1 # l 左边界，r 右边界 l,r = 0,length-1 # l 与 r 相等时结束循环 while l<r: # 取中值 mid = (r+l)//2 # 如果中值处为目标值，直接返回 if nums[mid]==target: return mid # 如果边界处为目标值，也直接返回 if nums[l]==target: return l if nums[r]==target: return r # 如果左边界小于中点的值，说明左部是正常排序 if nums[l]<nums[mid]: # 若此时目标值在左部，将右边界缩到 mid-1 if nums[l]<target and target < nums[mid]: r = mid-1 # 否则调整左边界到 mid+1 else: l = mid+1 # 右部正常排序的情况 else: # 若目标值位于右部，调整左边界到 mid+1 if nums[mid]<target and target < nums[r]: l = mid+1 # 否则，调整右边界 else: r = mid-1 # 若上述过程循环完仍未取到目标值，说明没有，返回 -1  return -1

执行用时 : 32 ms, 在所有 Python3 提交中击败了 97.01% 的用户内存消耗 : 13.9 MB, 在所有 Python3 提交中击败了 7.69% 的用户

示例 1:输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]
示例 2:输入: nums = [5,7,7,8,8,10], target = 6输出: [-1,-1]

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: length = len(nums) # 特殊情况处理 if length<2: # 单数列表，且该数与目标值相等 if nums and nums[0]==target: return [0,0] # 不匹配的单数列表、空列表 else: return [-1,-1] # 目标值超出列表值范围情况 if target<nums[0] or target>nums[-1]: return [-1,-1] # 先定义好默认值 left,right = -1,-1 # 起始位置的二分查找开始 l,r = 0,length-1 # 老样子，while 循环 while l<r: # 取中点 mid = (l+r)//2 # 若中点小于目标值，调整左边界至 mid+1 # 因为取中点偏左边界，所以可以不取 mid 直接下一位 mid+1，即使 mid+1 真就是起始位置，也可以通过取中点取到该处 if nums[mid]<target: l = mid+1 # 若中点值大于等于目标，因为我们要找目标的起点，所以把右边界调整到 m # 不取 mid-1 的原因在于，若 mid-1 为起点，把其作为右边界的话，无法通过取中点定位到该位置 elif nums[mid]>=target: r = mid # while 循环结束时，l 即起点位置，这时要检查下列表中该位置是否存在目标值 # 若列表该位置确实存在目标值，更新起始位置到 left if nums[l]==target: left = l # 若不存在，列表中没有目标值，返回 -1 相关结果 else: return [-1,-1] # 接下来找结束位置 # 若此时已经是最后一位，那么结束位置与起始位置相同，直接返回 if l+1==length: return [left,left] # 若后续还有其它位，重新开启二分查找 # 取起始位置下一位开始作为边界 l,r = l+1,length-1 while l<r: mid = (l+r)//2 # 如果中点值大于目标，更新右边界为 mid if nums[mid]>target: r = mid # 如果中点值小于等于目标，将左边界更新 elif nums[mid]<=target: l = mid+1  # 当while循环结束时，有可能 l 是结束位置，也可能是结束位置的下一位 # 若为结束位置  if nums[l]==target: right = l # 若其上一位是结束位置 elif nums[l-1]==target: right = l-1 # 将更新完毕的位置返回 return[left,right]

执行用时 : 40 ms, 在所有 Python3 提交中击败了 81.86% 的用户内存消耗 : 14.6 MB, 在所有 Python3 提交中击败了 7.69% 的用户