這題主要運用到二分搜尋法,是 704. Binary Search 的變化題,目標是找到一個旋轉陣列中指定元素的陣列,用到一個 while 迴圈和其餘 if 判斷,時間複雜度估 O(log n)
,這裡有 JAVA 和 Python 的寫法。
There is an integer array
nums
sorted in ascending order (with distinct values).
Prior to being passed to your function,nums
is possibly rotated at an unknown pivot indexk
(1 <= k < nums.length
) such that the resulting array is[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(0-indexed). For example,[0,1,2,4,5,6,7]
might be rotated at pivot index3
and become[4,5,6,7,0,1,2]
.
Given the arraynums
after the possible rotation and an integertarget
, return the index oftarget
if it is innums
, or-1
if it is not innums
.
You must write an algorithm withO(log n)
runtime complexity.
有一個整數陣列
nums
已升序排序 (且具不同的值)。
在傳遞給你的函數之前,nums
可能在一個未知的樞軸索引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]
可能會在樞軸 3 處旋轉並變成[4,5,6,7,0,1,2]
。
給定一個可能的旋轉後的陣列nums
和一個整數target
,如果target
它在nums
中就回傳target
的索引, 如果它不在nums
中就回傳-1
。
你必須寫出一個O(log n)
時間複雜度的演算法。
題目連結:https://leetcode.com/problems/search-in-rotated-sorted-array/
1 <= nums.length <= 5000
104 <= nums[i] <= 104
All values of nums
are unique.nums
is an ascending array that is possibly rotated.104 <= target <= 104
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Input: nums = [1], target = 0
Output: -1
這題用的技巧是二分搜尋法,原理是每次循環都會將陣列搜索範圍縮小一半,目的是要找到 target 值的 index
- 初始我們會設定起點位置、終點位置、中間點 (這些是二分搜尋法的必要條件)
middle = start + ( end - start ) / 2
可取得中間點- 如果整個陣列都是有序的,那麼目標整數 target 必然存在於該有序的部分,我們可以直接進行二分搜尋找到目標值,但這題比較麻煩的是我們不知道陣列會旋轉成什麼樣子,所以先判斷陣列的左邊還是右邊是否有序
- 如果那半邊是有序的,就在那半邊使用二分搜尋法做搜尋
- 如果 target 不在那半邊的話,則會轉向另一邊做搜尋
- 直到 start 大於等於 end,表示搜尋範圍為空,結束搜尋
- 到最後範圍會縮到最小,起點值和目標值一定會重疊,然後回傳答案索引
[注意點] 之所以要用上述中間點的寫法會比較安全,因如果 start 和 end 趨近於最大數時,兩者相加起來的合可能會造成整數溢位
class Solution {
public int search(int[] nums, int target) {
int start = 0; // 起點位置
int end = nums.length - 1; // 終點位置
while (start < end) {
int middle = start + (end-start)/2; // 中間點
if (nums[middle] == target) return middle; // 剛好中間點就是答案就回傳
// 判斷左半邊是有序的
if (nums[start] <= nums[middle]) {
// 如果 target 在左半邊的範圍內,則繼續在左半邊進行搜尋
if (target >= nums[start] && target < nums[middle]) {
// 重新定義終點,下次回圈找到新的終點就好
end = middle - 1;
// 否則,轉向右半邊進行搜尋
} else {
// 重新定義起點,下次回圈從新的起點開始就好
start = middle + 1;
}
// 否則,右半邊是有序的
} else {
if (target > nums[middle] && target <= nums[end]) {
start = middle + 1;
} else {
end = middle - 1;
}
}
}
// 到最後範圍會縮到最小,起點值和目標值一定會重疊,就回傳索引
return nums[start] == target ? start : -1;
}
}
使用了和 Java 一樣的邏輯執行,換成 Python 的寫法
不一樣的點是變數的宣告方式不一樣,還有 Java 和 Python 的三元運算寫法不一樣
class Solution:
def search(self, nums: List[int], target: int) -> int:
start, end = 0, len(nums) - 1 # 起點、終點
while start < end:
middle = start + (end - start) // 2 # 中間點
# 中間點是答案就回傳
if nums[middle] == target
return middle
# 判斷左半邊是有序的
if nums[start] <= nums[middle]:
# 如果 target 在左半邊的範圍內,則繼續在左半邊進行搜尋
if nums[start] <= target and target < nums[middle]:
end = middle - 1
else:
start = middle + 1 # 否則,轉向右半邊進行搜尋
# 否則,右半邊是有序的
else:
if nums[middle] < target and target <= nums[end]:
start = middle + 1
else:
end = middle - 1
# 如果 start == target 回傳 start 否則回傳 -1
return start if nums[start] == target else -1
Language | Runtime | Memory |
---|---|---|
Java | 0ms | 41.2MB |
Python | 54ms | 16.75MB |
(新手上路,如有錯誤請友善告知,感謝)
Blog
https://chris81051.github.io/2023/08/01/LeetCode-33-Search-in-Rotated-Sorted-Array-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論