[LeetCode] #33. Search in Rotated Sorted Array

-

題目

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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 index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

直覺解

構想：

用二分法找到中斷點（沒有依照遞增排列的那個點），例如 [4,5,6,7,0,1,2] 的中斷點的 index 是 4，如果在尋找中斷點的過程中就先發現 target，則直接回傳 target 的 index。判斷 target 在中斷點的左邊還是右邊後，再用二分法找 target 的 index。

為了避免尋找中斷點時，index 超出 list 的範圍，長度是 1 的 list 就不執行 find_pivot 函式了。

我的變數命名的不太好，雖然取名叫 pivot，但是意思跟題目說的 pivot 不一樣。以 [4,5,6,7,0,1,2] 而言，題目說的 pivot 是指「[0,1,2,4,5,6,7] is rotated at pivot index 3」，我的意思則是「在 index 4 的地方，[4,5,6,7,0,1,2] 被切成了兩段遞增數列」。

python 3 實作：

class Solution: 

    def search(self, nums: List[int], target: int) -> int: 

        if target < nums[0] and target > nums[-1]: 

            return -1 

         

        if len(nums) == 1: 

            if nums[0] == target: 

                return 0 

            return -1 

         

        target_index, pivot = self.find_pivot(nums, target) 

        if target_index is not None: 

            return target_index 

        min = 0 

        max = len(nums) - 1 

        if target < nums[0]: 

            min = pivot + 1 

        else: 

            max = pivot - 1 

 

        while min <= max: 

            mid = (min + max) // 2 

            if nums[mid] == target: 

                target_index = mid 

                break 

            elif nums[mid] < target: 

                min = mid + 1 

            else: 

                max = mid - 1 

        else: 

            target_index = -1 

             

        return target_index 

     

    def find_pivot(self, nums: List[int], target: int) -> tuple: 

        target_index = None 

        pivot = None 

        # no pivot 

        if nums[-1] > nums[0]: 

            return (target_index, len(nums)) 

         

        # there is a pivot 

        min = 0 

        max = len(nums) - 1 

        while min <= max: 

            mid = (min + max) // 2 

            if nums[mid] == target: 

                target_index = mid 

                break 

 

            if nums[mid] < nums[mid-1]: 

                pivot = mid 

                break 

 

            if nums[mid] < nums[0]: 

                max = mid - 1 

            else: 

                min = mid + 1 

 

        return (target_index, pivot)

效能：

Runtime: 44 ms, faster than 43.18% of Python3 online submissions for Search in Rotated Sorted Array.
Memory Usage: 14.6 MB, less than 55.97% of Python3 online submissions for Search in Rotated Sorted Array.

實作過程中犯過的錯誤

  • 我的寫法預設有中斷點，但有些 nums 沒有中斷點，例如 [1,2,3,4,5,6]。

  • 中斷點的判斷方式錯誤。原本以為「中斷點比左右兩邊的數都小」；後來發現不用那麼複雜，只要「中斷點比左邊的數小」就夠了。

研究別人的解

來源：sample 40 ms submission

研究重點：我的寫法又臭又長，想看更簡潔的寫法。

別人的 python 3 實作：

class Solution: 

    def search(self, nums: List[int], target: int) -> int: 

        l, r = 0, len(nums) - 1 

        while l + 1 < r: 

            mid = (l + r) // 2 

            if target == nums[mid]: 

                return mid 

             

            if nums[mid] > nums[l]: 

                if nums[l] <= target < nums[mid]: 

                    r = mid 

                else: 

                    l = mid 

            else: 

                if nums[mid] < target <= nums[r]: 

                    l = mid 

                else: 

                    r = mid 

        if nums[l] == target: 

            return l 

        elif nums[r] == target: 

            return r 

        else: 

            return -1

效能：

Runtime: 40 ms, faster than 72.88% of Python3 online submissions for Search in Rotated Sorted Array.
Memory Usage: 14.7 MB, less than 55.97% of Python3 online submissions for Search in Rotated Sorted Array.

研究感想

nums 可能會從中斷點處，被切成兩段嚴格遞增數列。右邊那段遞增一定比左邊那段小。把他的其中一段程式碼拿出來看：

if nums[mid] > nums[l]: # 代表 l 和 mid 在同一段遞增裡面

    if nums[l] <= target < nums[mid]:  # 代表 target 和 l , mid 在同一段遞增裡面

        r = mid 

    else: # 不確定 target 和 r 是否在「l 和 mid 所在的那段遞增」裡面，

          # 但反正一定不會在「l~mid」這個範圍裡 

        l = mid 

else: # 代表 l 在左段遞增裡，mid 在右段遞增裡

    if nums[mid] < target <= nums[r]: # 代表 target 和 mid, r 在同一段遞增裡面

        l = mid 

    else: # 不確定 target 和 l 是否在「mid 和 r 所在的那段遞增」裡面，

          # 但反正一定不會在「mid~r」這個範圍裡

        r = mid

取了 mid 以後， l~mid 或 mid~r 這兩個範圍的其中一個，一定是在同一段嚴格遞增裡面。根據 target 是否在這段嚴格遞增裡面，決定縮減右邊範圍還是左邊範圍。

以前寫的題目，l, r, target 都在同一段嚴格遞增裡面，所以我的直覺解也習慣性地想要保持讓 l, r, target 都在同一段嚴格遞增裡面，所以非得要先查出中斷點在哪裡，我才有辦法設定 l 和 r 的 index。但是看完這個人的解，我才發現，原來，即使沒有「l, r, target 都在同一段嚴格遞增裡面」這樣的情報，也還是能找到 target。原來要找到 target 所需的情報，比我原本以為的還要少。我真是開了眼界了！

腦洞：如果被切成三段嚴格遞增的話，要怎麼找到 target？例如 [8,9,10,4,5,6,7,0,1,2] 之類的？

while 迴圈後面的 if- elif- else 可不可以拿掉

為什麼 while 的條件是 l + 1 < r（而不是 l <= r 或 l < r）。一開始我以為，這是為了避免 l, r, mid 超出 nums 的 index 範圍，不過仔細看的話，他的寫法， 是不會超出 index 範圍的。我試著把他的程式碼改成這樣：

class Solution: 

    def search(self, nums: List[int], target: int) -> int: 

        l, r = 0, len(nums) - 1 

        while l <= r: 

            mid = (l + r) // 2 

            if target == nums[mid]: 

                return mid 

             

            if nums[mid] > nums[l]: 

                if nums[l] <= target < nums[mid]: 

                    r = mid - 1 

                else: 

                    l = mid + 1 

            else: 

                if nums[mid] < target <= nums[r]: 

                    l = mid + 1 

                else: 

                    r = mid - 1 

        return -1

Wrong Answer

Input:
[3,1]
1

Output: -1

Expected: 1

r 變成 -1 結果就跳出迴圈 return -1 了。

參考下方的 sample 28 ms submission 再次改良，終於成功把 if- elif- else 拿掉了，關鍵點在於把 nums[mid] > nums[l] 改成 nums[mid] >= nums[l]：

class Solution: 

    def search(self, nums: List[int], target: int) -> int: 

        l, r = 0, len(nums) - 1 

        while l <= r: 

            mid = (l + r) // 2 

            if target == nums[mid]: 

                return mid 

 

            if nums[mid] >= nums[l]: 

                if nums[l] <= target < nums[mid]: 

                    r = mid - 1 

                else: 

                    l = mid + 1 

            else: 

                if nums[mid] < target <= nums[r]: 

                    l = mid + 1 

                else: 

                    r = mid - 1 

        return -1

效能：

Runtime: 32 ms, faster than 97.67% of Python3 online submissions for Search in Rotated Sorted Array.
Memory Usage: 14.7 MB, less than 55.97% of Python3 online submissions for Search in Rotated Sorted Array.

多一個等號，就從原本的 r = mid - 1 變成 l = mid + 1。一個等號就關係著能不能把 if- elif- else 拿掉，真是精細。

研究別人的解

來源：sample 28 ms submission

研究重點：上一個解，while 迴圈後面的 if- elif- else 可不可以拿掉。

別人的 python 3 實作：

class Solution: 

    def search(self, nums: List[int], target: int) -> int:

        left, right = 0, len(nums) - 1



        while left <= right:

            mid = (left + right) // 2



            if nums[mid] == target:

                return mid



            if nums[left] <= nums[mid]:

                if nums[left] <= target <= nums[mid]:

                    right = mid - 1

                else:

                    left = mid + 1



            else:

                if nums[mid] <= target <= nums[right]:

                    left = mid + 1

                else:

                    right = mid - 1



        else:

            return -1

效能：

Runtime: 44 ms, faster than 43.98% of Python3 online submissions for Search in Rotated Sorted Array.
Memory Usage: 14.7 MB, less than 24.23% of Python3 online submissions for Search in Rotated Sorted Array.

Comments

Post a Comment

Popular posts from this blog

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more