問題描述
給定一個升序排序的整數數組 nums 和一個目標值 target，請找出目標值應插入的位置，保證插入後數組仍然是有序的。
必須設計一個演算法，其時間複雜度為 O(log n)。
範例 1
輸入: nums = [1,3,5,6], target = 5
輸出: 2
範例 2
輸入: nums = [1,3,5,6], target = 2
輸出: 1
範例 3
輸入: nums = [1,3,5,6], target = 7
輸出: 4
範例 4
輸入: nums = [1,3,5,6], target = 0
輸出: 0
解法一：二分搜尋法
思路
由於數組是已經排序的，可以使用二分搜尋法來快速定位 target 應插入的位置：
- 設置兩個指針
left和right，初始分別為數組的開頭與結尾。 - 計算中間索引
mid： - 如果
nums[mid] == target，則直接返回mid。 - 如果
nums[mid] < target，則目標值應該在右半部分，調整left = mid + 1。 - 如果
nums[mid] > target，則目標值應該在左半部分，調整right = mid - 1。
- 如果
- 當
left > right時，left即為目標值應插入的位置。
程式碼
class Solution:
def searchInsert(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
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
時間與空間複雜度
- 時間複雜度：O(log n)，二分搜尋法每次將搜尋範圍縮小一半。
- 空間複雜度：O(1)，只使用了常數空間。
解法二：線性掃描法
思路
直接從左到右遍歷數組，當找到第一個比 target 大的元素時，返回其索引。如果遍歷到最後都沒有找到，則目標值應插入數組末尾。此方法簡單，但不符合題目時間複雜度為 O(log n)的要求。
程式碼
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] >= target:
return i
return len(nums)
時間與空間複雜度
- 時間複雜度：O(n)，需要遍歷整個數組。
- 空間複雜度：O(1)。
解法三：內建函數
思路
Python 提供了 bisect 模組，可以直接用於查找目標值的插入位置。bisect_left 函數返回目標值的插入位置，並保證插入後數組仍然有序。
程式碼
import bisect
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect.bisect_left(nums, target)
時間與空間複雜度
- 時間複雜度：O(log n)，
bisect_left使用二分搜索實現。 - 空間複雜度：O(1)。
結論
- 最佳解法：使用 解法一（二分搜尋法），能滿足 O(log n) 的時間複雜度要求，並且實現簡潔。
- 次佳解法：對於小規模數據，可以使用 解法二（線性掃描法），但不適合大數據量。
- 內建函數解法：如果使用 Python，解法三（
bisect模組） 提供了一個簡潔的實現。
建議在實際開發中，優先採用 解法一 或 解法三。
