題目解釋
有一個按 ascending sorted 的整數 array nums
(每個值都是 unique 的)。
nums
可能會在未知的 pivot index k
(1 <= k < nums.length
) 處進行旋轉,
使得結果數組為 [nums[k], nums[k+1], ... , nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(從 0 開始)。
例如,[0, 1, 2, 4, 5, 6, 7]
可能會在 pivot index 3
處旋轉並變為 [4, 5, 6, 7, 0, 1, 2]
。
給定可能旋轉後的陣列 nums
和整數 target
,如果目標在 nums
中,則傳回 target
的 index,如果不在 nums
中,則傳回 -1
。
您必須編寫一個在 O(log n) 時間內執行的演算法。
範例
- 輸入:
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
- 輸出:
4
目標 0
在 nums
的第 4
個位置。
最佳解法
看到
O(log n)
就要反射性的想到二元搜尋法 (Binary Search)!
這題跟 153. Find Minimum in Rotated Sorted Array 真的很像。
但是我自己就有一個疑問,就是為什麼在 153. Find Minimum in Rotated Sorted Array 用的邏輯到這題來卻會不正確。
明明他們同樣都是把 sorted array 給 pivot,
因此 array 裡面總是會有一部分是 sorted 的一部分是 unsorted 的,
只不過一個是找最小值一個是搜尋?
細探之後才了解這兩題運用到的性質其實不太一樣,
這題簡單來說邏輯就是先切左右兩邊(left ~ mid
與 mid ~ right
),
確認哪一邊是 sort 過的,
如果 target 的值在 sort 過的那一塊的範圍的話,
就在那邊繼續找,否則就找另一邊。
而 153. Find Minimum in Rotated Sorted Array 則是經過窮舉所有場景所 summarize 出來的經驗法則 (?),
因為只關心最小值在哪。
步驟
- 先切左右兩邊
left
~mid
mid
~right
- 確認哪一邊是 sort 過的
- 如果 target 的值在 sort 過的那一塊的範圍的話
=> 在那邊繼續找 - 否則
=> 找另一邊
程式碼
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while (left <= right):
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
其實我覺得註解寫在旁邊好像比較好懂…給大家參考看看。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while (left <= right):
mid = left + (right - left) // 2
if nums[mid] == target: # mid == target
return mid
elif nums[left] <= nums[mid]: # left side is sorted
if nums[left] <= target < nums[mid]: # target in sorted left side
right = mid - 1 # shrink left side range
else:
left = mid + 1 # find another side (right)
else: # right side is sorted
if nums[mid] < target <= nums[right]: # target in sorted right side
left = mid + 1 # shrink right side range
else:
right = mid - 1 # find another side (left)
return -1
時間複雜度
O(logn)
,n 是 nums
的元素個數。
空間複雜度
O(1)
。
結語
好棒,python 可以直接寫 a < b < c
的形式,
查了一下才知道這種運算式的正確術語叫做「鏈式比較」(Chained Comparison
),
又是已知用火的一天🔥
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26