LeetCode

Appearance

81. Search in Rotated Sorted Array II ​

题目 ​

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

 

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

 

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

 

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Related Topics
  • 数组
  • 二分查找

  • 👍 842
  • 👎 0

    • 解法 ​

    无重复元素时，根据 nums[left] nums[mid] nums[right] 之间的大小关系，可判断左边是升序或者右边是升序 有重复元素时，以左边为出发判断左边是否有序，分别是两种情况，

    • nums[left] < nums[mid] 判断左边是升序数组
    • num[left] = nums[mid] 左边可能是升序，或者是平序，需要对 left 进行收缩

    当判断左边状况后，即可确定 mid -> right 状况

    python
    class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target or nums[left] == target or nums[right] == target:
                return True

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

        return False

    复杂度分析 ​

    • 时间复杂度O(logN) - O(N)
    • 空间复杂度O(1)

    优化解法 ​

    • 只有 num[left] = nums[right] = nums[mid] 的情况下才无法根据 nums[mid] 大小判断出升序或者降序
    • 将每次判断 num[left]、nums[right]和 target 的对比放入循环内
    py
    from typing import List

# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return True

            if nums[mid] == nums[left] == nums[right]:
                left += 1
                right -= 1

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

        return False

        
# leetcode submit region end(Prohibit modification and deletion)
Solution().search([3,1], 1)

    复杂度分析 ​

    • 时间复杂度O(logN) - O(N)
    • 空间复杂度O(1)