[LeetCode解題攻略] 34. Find First and Last Position of Element..

問題描述

給定一個按升序排序的整數數組 nums 和一個目標值 target，請在數組中找到目標值的 第一個 和 最後一個 位置，並以一個長度為 2 的列表返回結果。如果數組中不存在目標值，返回 [-1, -1]。

限制條件

• 數組 nums 的長度範圍為 0 <= nums.length <= 10^5。
• 數組中的數字範圍為 -10^9 <= nums[i] <= 10^9。
• nums 保證為非遞減排序。

範例1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

範例2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

範例3:

Input: nums = [], target = 0
Output: [-1,-1]

解法一：二分搜索

思路

由於數組是排序的，可以利用二分搜索來高效地定位目標值的 左邊界 和 右邊界。

步驟

1. 找到左邊界：使用二分搜索法，當目標值與中間值相等時，繼續搜索左半部分。
2. 找到右邊界：使用二分搜索法，當目標值與中間值相等時，繼續搜索右半部分。
3. 如果找不到目標值，返回 [-1, -1]。

程式碼

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findLeft(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        def findRight(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right

        left = findLeft(nums, target)
        right = findRight(nums, target)

        # 確保 target 存在於數組中
        if left <= right and left < len(nums) and nums[left] == target:
            return [left, right]
        else:
            return [-1, -1]

時間與空間複雜度

• 時間複雜度：O(log n)，兩次二分搜索的時間複雜度加起來為 O(log n)。
• 空間複雜度：O(1)，只使用常數額外空間。

解法二：線性掃描

思路

遍歷整個數組，記錄目標值的第一次和最後一次出現的位置。該方法不符合 O(log n) 的要求，但實現簡單。

程式碼

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start, end = -1, -1
        for i in range(len(nums)):
            if nums[i] == target:
                if start == -1:
                    start = i
                end = i
        return [start, end]

時間與空間複雜度

• 時間複雜度：O(n)，需要遍歷整個數組。
• 空間複雜度：O(1)。

解法三：內建函數

思路

利用 Python 的內建函數 bisect 模組，分別找到目標值的左邊界和右邊界。

程式碼

import bisect

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect.bisect_left(nums, target)
        right = bisect.bisect_right(nums, target) - 1

        if left <= right and left < len(nums) and nums[left] == target:
            return [left, right]
        else:
            return [-1, -1]

時間與空間複雜度

• 時間複雜度：O(log n)，bisect_left 和 bisect_right 都是基於二分法。
• 空間複雜度：O(1)。

結論

1. 解法一（二分搜索）是本題的最佳解法，符合 O(log n) 的時間複雜度要求。
2. 解法二 適合小規模數據，雖然簡單易實現，但時間效率較低。
3. 解法三 利用 Python 的內建函數，在特定語言環境中可以快速實現。

如果目標是最優解法，建議使用 解法一。