【Leetcode 筆記】153. Find Minimum in Rotated Sorted Array

題目解釋

假設有一 ascending sorted 的 array 在 1 到 n 次之間旋轉。
例如，陣列 nums = [0, 1, 2, 4, 5, 6, 7] 可能會變成：

• 旋轉 4 次 -> [4, 5, 6, 7, 0, 1, 2]
• 旋轉 7 次 -> [0, 1, 2, 4, 5, 6, 7]

注意，將 array = [a[0], a[1], a[2], ..., a[n-1]] 旋轉 1 次會得到 [a[n-1], a[0] , a[1], a[2], ..., a[n-2]]。 給定唯一元素的排序旋轉陣列 nums，傳回該陣列的最小元素。

您必須編寫一個在 O(log n) 時間內執行的演算法。

範例

• 輸入: nums = [3, 4, 5, 1, 2]
• 輸出: 1

原始 array [1, 2, 3, 4, 5] 旋轉了 3 次，在此 array 中，最小的 element 是 1。

最佳解法

看到 O(log n) 就要反射性的想到二元搜尋法 (Binary Search)！

步驟

我們可以先窮舉出所有可能的例子，如下圖。

我們可以歸納出一個通用的規則。

• if 找左
  • [mid] < [right]
• if 找右
  • [left] < [mid]
• if [mid] 恰巧就是 min 值
  • [mid] < [right] 且 [mid] < [mid – 1]

上面規則又可以縮減為：

    if [mid] < [right]
        if [mid] 恰巧就是 min 值
            回傳 [mid] 的值
        else
            找左
    else
        找右

至此，其實 code 也就寫完了🎉

唯一要注意的就是雖然 array 裡面都是 distinct 的值，
但是因為可能會遇到類似 [1] 的 情況，如果不把條件式設為包含 "=" 的話就會噴 error。

程式碼

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while (left <= right):
            mid = left + (right - left) // 2
            if nums[mid] <= nums[right]:
                if (nums[mid] <= nums[mid - 1]):
                    return nums[mid]
                else:
                    right = mid - 1
            else:
                left = mid + 1

時間複雜度

O(logn)，n 是 nums 的元素個數。

空間複雜度

O(1)。

結語

一題乍看之下完全沒頭緒的題目，一定要練習畫圖！

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！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