一魚多吃 用二分搜尋法 找目標值 Find in Mountain Array_Leetcode #1095

閱讀時間約 6 分鐘

這題的題目在這裡:

題目敘述

題目會給我們一個山形的輸入陣列,和目標值target,要求我們找出目標值所在的陣列索引。如果出現兩次,返回比較小的那一個,也就是比較靠左的那個索引值。

山形的意思就是說,從最左側到山頂最大值都是遞增,從山頂最大值到右側都是遞減。

You may recall that an array arr is a mountain array if and only if:

  • arr.length >= 3
  • There exists some 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]
raw-image

測試範例

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() <= 104
  • 0 <= target <= 109
  • 0 <= mountain_arr.get(index) <= 109

演算法

這題也是屬於二分搜尋法的應用題。
因為題目已經說是山形陣列,我們可以先用二分搜尋法找出最大值,也就是山頂。如同前面這題我們學過的技巧,來找山形陣列的絕對最大值。

找到山頂之後,整個陣列可以分成兩塊,左邊這塊剛好都是遞增的分布,右邊這塊剛好都是遞減的分布。不論是在左邊找,還是在右邊找,都是在已經排序好的子陣列尋找目標值,恰好符合二分搜尋法的應用場景。

接著先找左邊這塊,假如左邊這塊找不到再找右邊這塊;如果,最後還是找不到,就返回-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)


關鍵知識點

在已經排序好的陣列尋找目標值,聯想到二分搜尋法,這是標準的二分搜尋法的應用場景。

建議回頭複習高度關聯的題目:

Binary search, 找絕對最大值, 找相對最大值


Reference:

[1] Python O( log n ) sol. based on variant binary-search, run-time 88%+ - Find in Mountain Array - LeetCode

88會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目給定一個已排序的輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目會給定一個2D 二維的矩陣,矩陣內的元素值代表對應的高度,要求我們找出相對最高點,也就是(大樓)高度大於N4 東、南、西、北 四個鄰居的索引值。 題目保證矩陣內相鄰的元素值都不相同,也又是相鄰的兩兩相比較,一定有一個比較高,有一個比較矮。
題目會給定一個陣列,陣列裡面的元素分布就像一座山峰。 最大值的左邊都是上坡段,最大值的右邊都是下坡段。 要求我們找出陣列裡面的絕對極大值(absolute max value)所在的陣列索引
題目會給定一個陣列,裡面有大有小,可以把數字的大小類比成高度 要求我們找出陣列裡面的相對極大值(relative max value)所在的陣列索引 也就是說當下這個元素,大於左邊鄰居的元素值,也大於右邊鄰居的元素值
這題的題目在這裡 題目會給定一個輸入整數x, 要求我們返回x的正整數平方根(取無條件捨去小數部分的正整數值)
題目會給我們一個排序好的矩陣matrix ,和一個目標值 target 要求我們在矩陣中尋找target,如果存在,返回True。 如果target 不存在,返回False 題目要求必須在O( log (m*n) )對數時間內完成 。
題目給定一個已排序的輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
題目會給定一個2D 二維的矩陣,矩陣內的元素值代表對應的高度,要求我們找出相對最高點,也就是(大樓)高度大於N4 東、南、西、北 四個鄰居的索引值。 題目保證矩陣內相鄰的元素值都不相同,也又是相鄰的兩兩相比較,一定有一個比較高,有一個比較矮。
題目會給定一個陣列,陣列裡面的元素分布就像一座山峰。 最大值的左邊都是上坡段,最大值的右邊都是下坡段。 要求我們找出陣列裡面的絕對極大值(absolute max value)所在的陣列索引
題目會給定一個陣列,裡面有大有小,可以把數字的大小類比成高度 要求我們找出陣列裡面的相對極大值(relative max value)所在的陣列索引 也就是說當下這個元素,大於左邊鄰居的元素值,也大於右邊鄰居的元素值
這題的題目在這裡 題目會給定一個輸入整數x, 要求我們返回x的正整數平方根(取無條件捨去小數部分的正整數值)
題目會給我們一個排序好的矩陣matrix ,和一個目標值 target 要求我們在矩陣中尋找target,如果存在,返回True。 如果target 不存在,返回False 題目要求必須在O( log (m*n) )對數時間內完成 。
你可能也想看
Google News 追蹤
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
Thumbnail
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案,以及相關演算法框架。主要目標是給定n個相異的元素,產生所有的子集合。
Thumbnail
題目敘述 給定兩個字串word1和word2,每次操作時,可以有三個選項 插入一個字元 刪除一個字元 替換一個字元 請問把word1轉換成word2的最小操作次數是多少? 題目的原文敘述 約束條件 Constraints: 0 <= word1.length, word2.le
Thumbnail
題目敘述 題目會給我們兩種無限量供應的骨牌Domino 和 Tromino,形狀分別如下 題目的輸入會有一個參數n。 可以任意旋轉方向進行拼接,請問最後拼成 2 x n 長方形區域的方法數有幾種? 例如 n = 3 時,拼成2 x 3 的長方形區域有五種方法。 題目的原文敘述
Thumbnail
題目敘述 題目會給定我們一個n值,要求我們列出從0 ~ n 之間,每個整數有幾個bit1,以陣列的形式返回答案。 例如n=3時 因為 0 = 0b 0 1 = 0b 1 2 = 0b 10 3 = 0b 11 輸出答案為[0, 1, 1, 2] 題目的原文敘述 測試範例 E
Thumbnail
題目敘述 題目會給定一個字串陣列arr最為輸入,我們可以任意選擇一組不包含重複字元的陣列子序列,將字串進行串接,成為字串s,請問字串s的最大長度是多少? 例如: arr=["dog","cow","cat"] 我們可以選擇"dog", "cat"進行串接,得到的字串s="dogcat",s的
關於一主多奴,奴寵部份也該注意什麼? 要完全站在奴寵位置思考,還是有點難😅 1.妳能夠在理解之後,打心底接受這樣的關係嗎? 這邊說的接受,不是不停洗腦自己去接受這樣的關係,而是真的能夠接受這樣的關係,理解跟接受是兩回事。 2.妳曾想過想要怎樣的同伴嗎? 因為有時候,可能是妳和她相處的時間
關於一主多奴,無論是主、奴哪方都需要注意的事項。 1.作為主人,你足夠坦誠嗎? 這邊指的坦誠,並不是指等你有了第一個奴一段時間,才突然坦承自己想要多收奴,而是一開始建立關係之前就必須告知讓奴方了解,這是義務,也是作為主人的責任。 在有第一位奴願意理解、接受之後,對後來遇到的第二位甚至往後幾位,
Thumbnail
很多的時候,大家都會認為一些成功者,都是很聰明的。【其實不然】。 阿里巴巴的創辦人馬雲,算是一位特別傳奇人物。 其中馬雲高中畢業,參加第一次高考(大學入學考試),大家應該不敢相信其中數學考了1分。
股票可以一魚多吃? 可以,我們熟知的股票,主要是做價差或領股息,但是您知道,還可以做什麼用途嗎? 假如我們不要把股票賣掉,所以不做價差,那麼股票就可以做以下用途。
Thumbnail
說過上餘裕的生活,其實和「財富自由」沒有絕對關係⋯⋯時常覺得夢想和快樂是世上最快被放棄東西,無論是現實勒緊褲袋、或成就地位束縛,是說得頭頭是道卻毫無價值,總是第一個被捨棄⋯⋯
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
Thumbnail
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案,以及相關演算法框架。主要目標是給定n個相異的元素,產生所有的子集合。
Thumbnail
題目敘述 給定兩個字串word1和word2,每次操作時,可以有三個選項 插入一個字元 刪除一個字元 替換一個字元 請問把word1轉換成word2的最小操作次數是多少? 題目的原文敘述 約束條件 Constraints: 0 <= word1.length, word2.le
Thumbnail
題目敘述 題目會給我們兩種無限量供應的骨牌Domino 和 Tromino,形狀分別如下 題目的輸入會有一個參數n。 可以任意旋轉方向進行拼接,請問最後拼成 2 x n 長方形區域的方法數有幾種? 例如 n = 3 時,拼成2 x 3 的長方形區域有五種方法。 題目的原文敘述
Thumbnail
題目敘述 題目會給定我們一個n值,要求我們列出從0 ~ n 之間,每個整數有幾個bit1,以陣列的形式返回答案。 例如n=3時 因為 0 = 0b 0 1 = 0b 1 2 = 0b 10 3 = 0b 11 輸出答案為[0, 1, 1, 2] 題目的原文敘述 測試範例 E
Thumbnail
題目敘述 題目會給定一個字串陣列arr最為輸入,我們可以任意選擇一組不包含重複字元的陣列子序列,將字串進行串接,成為字串s,請問字串s的最大長度是多少? 例如: arr=["dog","cow","cat"] 我們可以選擇"dog", "cat"進行串接,得到的字串s="dogcat",s的
關於一主多奴,奴寵部份也該注意什麼? 要完全站在奴寵位置思考,還是有點難😅 1.妳能夠在理解之後,打心底接受這樣的關係嗎? 這邊說的接受,不是不停洗腦自己去接受這樣的關係,而是真的能夠接受這樣的關係,理解跟接受是兩回事。 2.妳曾想過想要怎樣的同伴嗎? 因為有時候,可能是妳和她相處的時間
關於一主多奴,無論是主、奴哪方都需要注意的事項。 1.作為主人,你足夠坦誠嗎? 這邊指的坦誠,並不是指等你有了第一個奴一段時間,才突然坦承自己想要多收奴,而是一開始建立關係之前就必須告知讓奴方了解,這是義務,也是作為主人的責任。 在有第一位奴願意理解、接受之後,對後來遇到的第二位甚至往後幾位,
Thumbnail
很多的時候,大家都會認為一些成功者,都是很聰明的。【其實不然】。 阿里巴巴的創辦人馬雲,算是一位特別傳奇人物。 其中馬雲高中畢業,參加第一次高考(大學入學考試),大家應該不敢相信其中數學考了1分。
股票可以一魚多吃? 可以,我們熟知的股票,主要是做價差或領股息,但是您知道,還可以做什麼用途嗎? 假如我們不要把股票賣掉,所以不做價差,那麼股票就可以做以下用途。
Thumbnail
說過上餘裕的生活,其實和「財富自由」沒有絕對關係⋯⋯時常覺得夢想和快樂是世上最快被放棄東西,無論是現實勒緊褲袋、或成就地位束縛,是說得頭頭是道卻毫無價值,總是第一個被捨棄⋯⋯