程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Search in Rotated Sorted Array

LeetCode Search in Rotated Sorted Array

編輯:C++入門知識

LeetCode Search in Rotated Sorted Array


LeetCode解題之Search in Rotated Sorted Array


原題

把一個嚴格升序的數組進行旋轉,如[0,1,2,3,4,5]旋轉3位成為[3,4,5,0,1,2]。在這樣的數組中找到目標數字。如果存在返回下標,不存在返回-1。

注意點:

數組中不存在重復的數字 不知道數組旋轉了多少位

例子:

輸入: nums = [4, 5, 6, 7, 0, 1, 2], target = 6
輸出: 2

輸入: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
輸出: -1

解題思路

采用了二分搜索,不過旋轉後的數組要討論的情況增多了。其實旋轉後的數組的大小關系一般如下圖:

     /
    /
   /
  /
             /
            /
           /

先通過中點與左頂點的關系來分類討論中點落在了哪一部分,如果在左半邊,則繼續討論目標數在中點的左邊還是右邊;如果在右半邊,同樣討論目標數的位置。同時需要注意特殊情況只剩下兩個數時,例如[3,1],這時求出的中點也是3,如果中點不匹配,應考慮1。這種情況不好與上面的情況合並,單獨列出。

AC源碼

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] > nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[mid] < nums[left]:
                if nums[mid] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                left += 1
        return -1


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

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


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved