“”“此為跟隨@ 代碼隨想錄19th訓練營之學習進度，
感謝Carl大神提供如此豐富的學習教材”“”
Array 理論基礎
- Array是存放在memory空間上，相同類型數據的集合
- 數組的index都是從0開始
- 數組的元素不能刪，只能覆蓋 (leetcode: 27)
704. Binary Search
重點:
- 數列需有序，才可使用二分法
- 數列虛無重複元素
- 區間定義需一致 (left < right / left <= right)
代碼
# binary search (區間:左閉右閉)
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0,len(nums)-1 # target 在左閉右閉的區間內，即 [left, right]
while left <= right:
mid = (left+right) // 2
if nums[mid] > target:
right = mid-1 # 發現target在左區間，所以改區間為 [left, middle - 1]
elif nums[mid] < target:
left = mid+1 # 發現target在右區間，所以改區間為 [middle+1, right]
else:
return mid # 找到target, return index
return -1 #都沒找到目標值相關題目:
- 35. Search Insert Position
- 34. Find First and Last Position of Element in Sorted Array
- 69. Sqrt(x)
- 367. Valid Perfect Square
27. Remove Element
重點:
- 題目強調in-place，所以不能另建一個array來裝判斷後的值，需在同一array作業 => O(1)
- 由於array的元素在memory的地址中是連續的，故無法真的刪除，而是要用覆蓋的方式。
代碼:
暴力法
# brute force // time complexity: O(n^2) // space complexity: O(1)
n = len(nums)
i = 0
while i < n:
if nums[i] == target:
for j in range(i, n-1):
nums[j] = nums[j+1]
n -= 1
i -= 1
i +=1
return len(nums[:n])雙指針法
# two point // time complexity: O(n) // space complexity: O(1)
slow = 0
for fast in range(n):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return len(nums[:slow])相關題目:
