LeetCode Digest
5 分鐘 閱讀文 (大約 690 個字)

Search Insert Position

題目
思路：最直覺是直接 iterate nums，不過題目指定要 O(log n)，所以用 binary search 才能達到

  1. 設定左右兩個指標作為可能答案範圍：[left, right]，目標是移動這兩個指標，縮小答案範圍，直到我們找到答案或答案範圍縮到只剩 1 個為止

  2. while left < right: binary search 什麼時候需要繼續下去？只要符合這個條件，就繼續 binary search

    • 因為目標是把答案範圍縮小到一個，此時兩個指標必須重合

  3. 迴圈寫完後，檢查一下：最後 left 有可能會 > right 嗎？

    • left 要 > right，唯一可能是 left == right == mid 的情況配合 left = mid + 1，不過假如發生前者的情況就會跳出迴圈，所以不會有 left > right 的情況發生，也就是說如果跳出迴圈，當時的條件一定是 left == right

  4. 看看 while 把 left & right 收斂到最後幾個的時候，還會不會繼續收斂直到跳出迴圈，或是其實不會繼續收斂而發生無窮迴圈，關注下面兩行移動 left & right 的程式碼

    1
    2
    1. left = mid + 1
    2. right = mid

    1. 剩最後三個：此時 mid 會是中間那個，上面兩種操作都有助於收斂範圍

    2. 剩最後兩個：此時 mid == left，上面兩種操作一樣可以收斂範圍

    3. 剩最後一個：此時 left == right，跳出迴圈

      => 確保了不會造成無窮迴圈

Python 3 solution
1
2
3
4
5
6
7
8
9
10
11
def searchInsert(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums)  # 設定左右兩個指標作為可能答案範圍：[left, right]
    while left < right:
        mid = (left + right) // 2  # Python3 不會有 integer overflow 的問題，所以可以直接 (left + right)，然後用 `//` 無條件捨去，避免小數
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1  # 此時最小的可能答案為 `mid + 1`
        else:
            right = mid  # 此時最大的可能答案為 `mid`
    return left

參考文章：Come on, forget the binary search pattern/template! Try understand it!

  • 這篇的思路是有幫助的，但他一開始設定的可能答案範圍錯了，導致還需要 post processing，假如真的是答案範圍，那範圍裡只剩一個的時候，那個就是答案，不會需要 post processing。

類似題：

延伸題：Find Peak Element

#
Add Two Numbers
3Sum

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×