LeetCode Search for a Range

LeetCode解題之Search for a Range

原題

在一個有序的數組中找到找到目標數字的起始坐標和結束坐標，如果不存在則返回[-1, -1]。

注意點：

例子：

輸入: nums = [5, 7, 7, 8, 8, 10], target = 8
輸出: [3, 4]

輸入: nums = [5, 7, 7, 8, 8, 10], target = 6
輸出: [-1, -1]

解題思路

通過兩次二分法來獲的兩個邊界，左邊界的標志是中間數字為目標數字且它前面的數字不存在或不是目標數字；右邊界的標志是中間數字為目標數字且它後面的數字不存在或不是目標數字。如果沒有找到左邊界就可以確定不存在目標數字。需要注意邊界的操作。

AC源碼

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        result = []
        length = len(nums)

        start = 0
        end = length
        while start < end:
            mid = (start + end) // 2
            if nums[mid] == target and (mid == 0 or nums[mid - 1] != target):
                result.append(mid)
                break
            if nums[mid] < target:
                start = mid + 1
            else:
                end = mid
        if not result:
            return [-1, -1]

        end = length
        while start < end:
            mid = (start + end) // 2
            if nums[mid] == target and (mid == length - 1 or nums[mid + 1] != target):
                result.append(mid)
                break
            if nums[mid] <= target:
                start = mid + 1
            else:
                end = mid

        return result


if __name__ == "__main__":
    assert Solution().searchRange([5, 7, 7, 8, 8, 10], 8) == [3, 4]
    assert Solution().searchRange([5, 7, 7, 8, 8, 10], 5) == [0, 0]
    assert Solution().searchRange([5, 7, 7, 8, 8, 10], 7) == [1, 2]
    assert Solution().searchRange([5, 7, 7, 8, 8, 10], 10) == [5, 5]

歡迎查看我的Github來獲得相關源碼。