題目出處
難度
medium
題目分類
Array, Binary Search, Matrix
個人範例程式碼
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
l = 0 # left
r = m*n-1 # right
# matrix[idx//n][idx%n]
while(l <= r):
mid = (l+r)//2
if matrix[mid//n][mid%n] == target: # found
return True
elif matrix[mid//n][mid%n] < target: # mid smaller than target
l = mid+1
else: # mid bigger smaller than target
r = mid-1
return False
Time Complexity
O(logN)
Space Complexity
O(1)
算法說明
「查詢」的重要概念
這題帶出了「查詢的重要觀念」，
查詢這件事情基本上的時間複查度，
通常一般會是：
- O(n): 每一個都看過
- O(1): 有 hash map，用空間換取時間
這裡要來講一個特別的情況，當我們發現這個要查找的內容「有序或有規律」可尋，
也就是說，只要他「不是完全雜亂的」，
我們可以嘗試使用 binary search = O(logN)
這題目很明顯已經排好順序了，我們可以每次很輕鬆的進行對半切的動作，
這樣的概念就是「binary search」，之後在 tree 會更常使用。
處理成一維陣列
我們處理的重點就是在 binary search，
我們直接把這個矩陣當一個一維陣列來看，轉換方式為：
m = len(matrix)
n = len(matrix[0])
而 matrix[idx//n][idx%n] 的 idx 就可以代表我們想要的位置。
尋找過程
l = 0 # left
r = m*n-1 # right
我們找 mid = (l + r) //2
- 當 matrix[mid] target， 找到了!
- 當 matrix[mid] > target，我們比目標大，mid - 1
- 當 matrix[mid] < target， 我們還是比目標小，mid + 1
然後重複濃縮 mid 的範圍
直到 l >= r (因為一直有 +1 -1的操作)，遲早會重疊。
corner case 特殊情況處理
當只有一行時，需要注意處理 idx+1，idx-1 都會出錯
Boundary conditions/ Edge conditions 邊際情況處理
計算到 l >= r (因為一直有 +1 -1的操作)，遲早會重疊。