題目
給定一個按照升序排列的整數(shù)列表 nums譬挚，和一個目標值 target缠沈。請查找出給定目標值在列表中的開始位置和結(jié)束位置攻锰。
如果列表中不存在目標值 target揩魂，則返回 [-1, -1]。
例如：
給定一個列表 nums ：[5, 7, 7, 8, 8, 10]拐揭，target = 8
返回結(jié)果：[3, 4]給定一個列表 nums ：[5, 7, 7, 8, 8, 10]撤蟆，target = 6
返回結(jié)果：[-1, -1]給定一個列表 nums ：[]，target = 0
返回結(jié)果：[-1, -1]
實現(xiàn)思路1
- 定義2個變量：left_index堂污、right_index 家肯，分別表示開始位置和結(jié)束位置，默認值均為 -1
- 直接進行一輪遍歷盟猖，如果列表中存在目標值 target讨衣，那么就記錄第一個出現(xiàn)的位置换棚，并更新到 left_index、right_index反镇，如果在剩余列表元素中依然存在目標值 target固蚤，那么就只更新 right_index
代碼實現(xiàn)
class Solution:
def search_range(self, nums, target):
left_index, right_index = -1, -1
for i, value in enumerate(nums):
if value == target and left_index == -1:
left_index = i
if value == target:
right_index = i
return [left_index, right_index]
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
實現(xiàn)思路2
- 使用
二分查找來實現(xiàn) - 定義2個變量：left_index、right_index 歹茶，分別表示開始位置和結(jié)束位置夕玩，通過二分查找判斷，如果列表 nums 中不存在目標值 target惊豺，則直接返回 [-1, -1]燎孟，如果列表中存在目標值 target，并且查找出來的目標值下標為 index 尸昧，那么就將 left_index揩页、right_index 均更新為 index
- 在上面二分查找時，因為列表中可能存在多個相同元素烹俗，所以查找出來的 index 不一定是目標值 target 在列表中第一個出現(xiàn)的位置爆侣，因此需要對 left_index、right_index 做進一步處理
- 對于left_index幢妄，如果其左側(cè)的元素也等于目標值累提，即nums[left_index - 1] == target，那么就連續(xù)更新 left_index = left_index - 1磁浇，直到 left_index 恰為目標值在列表中第一個出現(xiàn)的下標位置
- 對于right_index，如果其右側(cè)的元素也等于目標值朽褪，即nums[right_index + 1] == target置吓，那么就連續(xù)更新 right_index = right_index + 1，直到 right_index 恰為目標值在列表中最后一個出現(xiàn)的下標位置
代碼實現(xiàn)
class Solution:
def search_range(self, nums, target):
index = self.binary_search(nums, target)
if index == -1: # 如果列表中不存在 target
return [-1, -1]
left_index, right_index = index, index
while left_index > 0 and nums[left_index - 1] == target: # 處理 left_index缔赠，找到第一個出現(xiàn)位置
left_index -= 1
while right_index < len(nums) - 1 and nums[right_index + 1] == target: # 處理 right_index衍锚，找到最后一個出現(xiàn)位置
right_index += 1
return [left_index, right_index]
def binary_search(self, nums, target): # 二分查找
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
return mid
return -1
從上面可以看到，如果列表中可能存在多個相同元素嗤堰，那么我們通過二分查找法查找返回的元素下標可能不是第一個出現(xiàn)位置戴质，因此，我們可以對上面的二分查找進行優(yōu)化：
- 在二分查找函數(shù) binary_search() 的參數(shù)中增加一個參數(shù)：flag
- 如果flag為True踢匣，那么表示查找列表nums中第一個大于等于target的下標
- 如果flag為False告匠，那么表示查找列表nums中第一個大于target的下標
優(yōu)化后的代碼如下：
class Solution:
def search_range(self, nums, target):
left_index = self.binary_search(nums, target, True) # 查找第一個大于等于target的索引
right_index = self.binary_search(nums, target, False) # 查找第一個大于target的索引
if left_index <= right_index - 1 and nums[left_index] == target and nums[right_index - 1] == target:
return [left_index, right_index - 1]
return [-1, -1]
def binary_search(self, nums, target, flag): # 改進后的二分查找
left, right, index = 0, len(nums) - 1, len(nums)
while left <= right:
mid = (left + right) // 2
if (nums[mid] > target) or (flag and nums[mid] >= target):
right = mid - 1
index = mid
else:
left = mid + 1
return index
- 時間復(fù)雜度：O(log n)
- 空間復(fù)雜度：O(1)
更多Python編程題，等你來挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）
