題目會給我們一個山形的輸入陣列,和目標值target,要求我們找出目標值所在的陣列索引。如果出現兩次,返回比較小的那一個,也就是比較靠左的那個索引值。
山形的意思就是說,從最左側到山頂最大值都是遞增,從山頂最大值到右側都是遞減。
You may recall that an array arr
is a mountain array if and only if:
arr.length >= 3
i
with 0 < i < arr.length - 1
such that:arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Example 1:
Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.
Example 2:
Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.
Constraints:
3 <= mountain_arr.length() <= 10
4
0 <= target <= 10
9
0 <= mountain_arr.get(index) <= 10
9
這題也是屬於二分搜尋法的應用題。
因為題目已經說是山形陣列,我們可以先用二分搜尋法找出最大值,也就是山頂。如同前面這題我們學過的技巧,來找山形陣列的絕對最大值。
找到山頂之後,整個陣列可以分成兩塊,左邊這塊剛好都是遞增的分布,右邊這塊剛好都是遞減的分布。不論是在左邊找,還是在右邊找,都是在已經排序好的子陣列尋找目標值,恰好符合二分搜尋法的應用場景。
接著先找左邊這塊,假如左邊這塊找不到再找右邊這塊;如果,最後還是找不到,就返回-1,代表找不到目標值。
class Solution:
def findPeak(self, mountain_arr) -> int:
left, right = 0, mountain_arr.length()-1
while left < right :
probe = left + ( right - left ) // 2
if mountain_arr.get(probe) > mountain_arr.get(probe+1):
right = probe
else:
left = probe + 1
return right
def findTarget(self, mountain_arr, peak_index, target) -> int:
# Phase_#1: Find Target in uphill
left, right = 0, peak_index
while left <= right:
probe = left + ( right - left ) // 2
probe_value = mountain_arr.get( probe )
if probe_value == target:
return probe
elif probe_value < target:
left = probe+1
else:
right = probe-1
# Phase_#2: Find Target in downhill
left, right = peak_index, ( mountain_arr.length()-1 )
while left <= right:
probe = left + ( right - left ) // 2
probe_value = mountain_arr.get( probe )
if probe_value == target:
return probe
elif probe_value < target:
right = probe-1
else:
left = probe+1
return -1
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
# Find mountain peak
peak_index = self.findPeak(mountain_arr)
# Find target in up-hill,then down-hill, or target does not exist in montain
index_of_target = self.findTarget( mountain_arr, peak_index, target)
return index_of_target
時間複雜度: O( log n)
都是用二分搜尋法來找最大值(山頂)和目標值(target)。
T(n) = T(n/2) + O(1),
T(n) = O( log n )
空間複雜度: O(1)
所用到的都是固定的臨時變數,所占用的記憶體空間為常數級別O(1)
在已經排序好的陣列尋找目標值,聯想到二分搜尋法,這是標準的二分搜尋法的應用場景。
建議回頭複習高度關聯的題目:
Reference: