題目

  • 題目連結
  • 目標函式 : search(nums, target)
    • Input : nums: List[int]、target: int
    • Output : int

解題概念

  • 題意 : 給定一升序排列的整數陣列 nums，該經過 Rotate 之後，若 target 在 nums 中回傳其索引值，否則回傳 -1
    • Rotate 動作 : 選某一未知數 k，使 nums 變成 : [nums[k], nums[k+1], ... , nums[n-1], nums[0], nums[1], ..., nums[k-1]]
    • 時間複雜度限制為 $O(\log n)$

我的寫法

  • 想法 : 只要找出 nums 中最小值的索引值 start，然後根據 target 可能位於 nums[:start] 或 nums[start:]，最後再去搜尋即可
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def search(self, nums, target):
        start = 0
        for i in xrange(1, len(nums)):
            if nums[i - 1] > nums[i]:
                start = i
                break

        # 特殊案例
        if start == 0 or start == len(nums) - 1: 
            return nums.index(target) if target in nums else -1
        if target == nums[0]: return 0

        # 判斷 target 可能位置
        if target > nums[0]:
            return nums.index(target) if target in nums[:start] else -1
        return nums.index(target) if target in nums[start:] else -1
  • 成效 :
    • Time Complexity : $O(n)$$O(\log n)$
    • Runtime: 22 ms (faster than 69.33%)
    • Memory Usage: 13.5 MB (more than 48.29%)

解答 or 其他優秀寫法

  • 想法 : 其實這題就是 Binary Search 的變形，總共需要做兩次搜尋，可分成三個 Stages 來處理 :

    • Stage 1 : 一樣找出 start
    • Stage 2 : 找出 target 會出現在 nums[0:start] 或 nums[start:] 中，進而調整 2nd Binary Search 的 left 與 `right

  • 程式碼 : 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    def search(self, nums, target):
        
        # Stage 1
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        start = left

        # Stage 2 

        left = 0
        right = len(nums) - 1
        if nums[start] <= target <= nums[right]:
            left = start
        else:
            right = start 

        # Stage 3 : 2nd Binary Search
        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 -1

  • 成效 :

    • Time Complexity : $O(\log n)$
    • Runtime: 25 ms (faster than 45.97%)
    • Memory Usage: 13.3 MB (more than 97.3%)