錯位排序陣列中找最小值

如果不管錯位,從頭跑到尾: O(n) ,也是會 Accepted ,不過很明顯這不是此題內涵:

需要好好思考,利用排序性:

  • 在未錯位的排序陣列,最小的在最左邊

我們期望的是直接回傳最左邊,基於這個想法,可以試著分割錯位的陣列,直到未錯位的子陣列之後,直接回傳最左邊。

那問題來了:

  • 怎樣知道在一個陣列內,有沒有錯位呢?

在錯位一次的狀況下,最左邊應該永小於最右邊

a[lo] < a[hi]

可以簡單地對半,遞迴核心虛擬碼:

findMin(nums) = min(findMin(LEFT(nums)), findMin(RIGHT(nums)) if (nums[i] > nums[j]) else nums[i]

這樣相當二元搜尋到錯位點 O(logn)。

答案:

此解相容於延伸題,不用更改:

這題要回答的是在有重複數值狀態下,最差狀況時間複雜度為何,為什麼

  • 平均複雜度是: O(logn)
  • 最差複雜度:O(n) 。因為最差切割到最小單位為止 O(n-1)。