歡迎關注 leetcode 專欄
題目
給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標值 target。找出給定目標值在數(shù)組中的開始位置和結束位置。
你的算法時間復雜度必須是 O(log n) 級別枫夺。
如果數(shù)組中不存在目標值，返回 [-1, -1]。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
鏈接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
解法
常規(guī)解法
思路：把一個問題拆分成兩個子問題：找左邊界 + 找右邊界上祈，解法都是一樣的，只是循環(huán)終止條件略有差異浙芙。
對于左邊界登刺，滿足以下條件時認為找到了：
- 值與 target 相同
- 左邊沒有其他值（即索引為0）或者左邊的值比 target 小
對于右邊界，滿足以下條件時認為找到了：
- 值與 target 相同
- 右邊沒有其他值（即索引為總長度 - 1）或者右邊的值比 target 大
# 常規(guī)解法
class Solution:
def searchRange(self, nums: int, target: int) -> int:
if not nums: return [-1, 1]
return [self.find_left_range(nums, target), self.find_right_range(nums, target)]
def find_left_range(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
middle = left + (right - left) // 2
if nums[middle] < target:
left = middle + 1
else:
if nums[middle] == target and (middle == 0 or nums[middle - 1] < target):
return middle
right = middle - 1
return -1
def find_right_range(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle - 1
else:
if nums[middle] == target and (middle == len(nums) - 1 or nums[middle + 1] > target):
return middle
left = middle + 1
return -1
空間復雜度 O(1)嗡呼，只是額外申請了幾個變量的空間纸俭。
時間復雜度 O(logn)，就是二分查找的復雜度南窗。
可以看出揍很，查找左右邊界的過程是分離的，所以也有優(yōu)化的空間矾瘾，也就是復用一部分結果女轿。比如先用二分查找法，在找到任意一個目標值時壕翩，對于此時的 left蛉迹、middle、right 放妈，分別使用 [left, middle] 作為查找左邊界的初始值北救，使用 [middle, right] 作為查找右邊界的初始值。不過芜抒，這種操作的復雜度沒變珍策，時間和空間上并沒有可見的改善。
遞歸解法
遞歸解法與常規(guī)解法相比而言宅倒，有一個容易犯錯的地方攘宙，就是當 nums[middle] == target 時，下一個遞歸的初始值要如何選擇拐迁。
- 當查找左邊界時蹭劈，如果 nums[middle] == target ，那么 middle 只能是新的臨時右邊界初始值线召；
- 當查找右邊界時铺韧，如果 nums[middle] == target ，那么 middle 只能是新的臨時左邊界初始值缓淹；
# 遞歸解法
class Solution:
def searchRange(self, nums: int, target: int) -> int:
if not nums: return [-1, -1]
return [self.find_left_range(nums, target, 0, len(nums) - 1),
self.find_right_range(nums, target, 0, len(nums) - 1)]
def find_left_range(self, nums, target, left, right):
if left > right: return -1
middle = left + (right - left) // 2
if nums[middle] == target and (middle == 0 or nums[middle - 1] < target):
return middle
elif nums[middle] < target:
return self.find_left_range(nums, target, middle + 1, right)
else:
return self.find_left_range(nums, target, left, middle - 1)
def find_right_range(self, nums, target, left, right):
if left > right: return -1
middle = left + (right - left) // 2
if nums[middle] == target and (middle == len(nums) - 1 or nums[middle + 1] > target):
return middle
elif nums[middle] <= target:
return self.find_right_range(nums, target, middle + 1, right)
else:
return self.find_right_range(nums, target, left, middle - 1)
空間復雜度 O(logn)哈打，最差情況下遞歸的深度就是logn塔逃。
時間復雜度 O(logn)，不變料仗。
Python專屬解法
python 的內置庫 bisect 湾盗，可以讓我們很方便地對有序列表進行操作。
這里主要使用兩個函數(shù)：
- bisect_left(nums, x)：對于 x罢维，找到在有序數(shù)組 nums 的合適插入位置（如果數(shù)組里有多個 x 則返回最左側的插入位置淹仑，即第一個 x 的索引），以保持有序肺孵。
- bisect_right(nums, x)：對于 x，找到有序數(shù)組 nums 的合適插入位置（如果數(shù)組里有多個 x 則返回最右側的插入位置颜阐，即最后一個 x 的索引 + 1）平窘，以保持有序。
import bisect
class Solution:
def searchRange(self, nums: int, target: int) -> int:
if not nums: return [-1, -1]
left = bisect.bisect_left(nums, target)
right = bisect.bisect_right(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
else:
return [left, right - 1]
還沒看過 bisect 庫的源碼凳怨，但一般 python 內置庫為了滿足各種場景的需要瑰艘，會額外加入一些異常處理邏輯，因此處理時間也會更長一些肤舞。
更多刷題紫新，盡在 leetcode 專欄
