[LeetCode解題攻略] 35. Search Insert Position

問題描述

給定一個升序排序的整數數組 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 應插入的位置：

1. 設置兩個指針 left 和 right，初始分別為數組的開頭與結尾。
2. 計算中間索引 mid：
3. • 如果 nums[mid] == target，則直接返回 mid。
   • 如果 nums[mid] < target，則目標值應該在右半部分，調整 left = mid + 1。
   • 如果 nums[mid] > target，則目標值應該在左半部分，調整 right = mid - 1。
3. 當 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)。

結論

1. 最佳解法：使用 解法一（二分搜尋法），能滿足 O(log n) 的時間複雜度要求，並且實現簡潔。
2. 次佳解法：對於小規模數據，可以使用 解法二（線性掃描法），但不適合大數據量。
3. 內建函數解法：如果使用 Python，解法三（bisect 模組） 提供了一個簡潔的實現。

建議在實際開發中，優先採用 解法一 或 解法三。