LeetCode 34: Find First and Last Position of Element in Sorted Array

問題描述

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

限制條件

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

範例

• Example 1:
  Input: nums = [5, 7, 7, 8, 8, 10], target = 8
  Output: [3, 4]
• Example 2:
  Input: nums = [5, 7, 7, 8, 8, 10], target = 6
  Output: [-1, -1]
• Example 3:
  Input: nums = [], target = 0
  Output: [-1, -1]

解法一：暴力解

解題思路

由於輸入參數 nums 已經遞增排序過了，所以最直覺的作法就是分別從首端跟尾端各迭代整個陣列一次，並記錄第一個遇到與 target 相同值的索引位置，並在最後回傳這兩個索引即可。

步驟詳解

1. 初始化 i, j 兩個指針，並分別從 0 及 len(nums) - 1 作為出發點。
2. 初始化 positions 為 [-1, -1] 用來作為紀錄找到的索引位置。
3. 首先從 i 開始依序迭代整個 nums，若 nums[i] 與 target 相同，將當前位置 i 記錄至 positions[0] 後中斷迭代。
4. 第二次迭代，從 j 開始反向迭代整個 nums，若 nums[j] 與 target 相同，將當前位置 j 記錄至 positions[1] 後中斷迭代。
5. 最後回傳 positions。

程式碼

def search_range(nums: List[int], target: int) -> List[int]:
    i = 0
    j = len(nums) - 1
    positions = [-1, -1]

    while i < len(nums):
        if nums[i] == target:
            positions[0] = i
            break
        i += 1

    while j >= 0:
        if nums[j] == target:
            positions[1] = j
            break
        j -= 1

    return positions

複雜度分析

• 時間複雜度：O(N)，其中 N 為 nums 的長度。
• 空間複雜度：O(1)。

解法二：二元搜尋法

解題思路

在題目中提到最優解的時間複雜度為 O(log N)，加上我們是要在一個已排序陣列中找到目標，所以這是很明確暗示我們使用二元搜尋法的提示。我們可以連續使用二元搜尋法兩次來逼近最近及最遠的兩個 target 來得到最後的答案。

步驟詳解

1. 初始化 positions 為 [-1, -1] 用來作為紀錄找到的索引位置。
2. 第一次二元搜尋：
   1. 分別初始化 left 及 right 雙指針為 0 及 len(nums) - 1 來界定搜索範圍。
   2. 當 left 小於等於 right 時：
      1. 計算 mid 位置 ((left + right) // 2)
      2. 若 nums[mid] 小於 target，將左指針 left 移至 mid + 1 的位置。
      3. 若 nums[mid] 大於 target，將右指針 right 移至 mid - 1 的位置。
      4. 若 nums[mid] 等於 target：
         1. 由於目前我們要找的是第一次出現 target 的位置，我們要檢查 mid 的前一個位置 (nums[mid - 1]) 是否也是 target，若是，將右指針 right 移至 mid - 1 的位置並繼續搜尋。
         2. 若否，表示我們已經找到第一次出現 target 的位置，將其記錄至 positions[0] 並中斷搜尋。
3. 第二次二元搜尋：
   1. 搜尋邏輯跟上面的第一次搜尋完全一樣，唯一不同的地方是由於這次我們要找的是最後一次出現 target 的位置，當 mid 指向的位置等於 target 且其後一個位置 (nums[mid + 1]) 也等於 target 時，將左指針 left 移至 mid + 1 的位置並持續搜尋。
4. 最後回傳 positions。

程式碼

def search_range(nums: List[int], target: int) -> List[int]:
    positions = [-1, -1]

    # find the first position
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            if mid > 0 and nums[mid - 1] == target:
                right = mid - 1
            else:
                positions[0] = mid
                break

    # find the last position
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            if mid < len(nums) - 1 and nums[mid + 1] == target:
                left = mid + 1
            else:
                positions[1] = mid
                break

    return positions

複雜度分析

• 時間複雜度：O(logN)，其中 N 為 nums 的長度。
• 空間複雜度：O(1)。

參考資料

• LeetCode 原題出處：Find First and Last Position of Element in Sorted Array – LeetCode