搜索旋转排序数组 II
- 难度： 中等
- 通过率： 32.5%
- 题目链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
进阶:
- 这是 搜索旋转排序数组 的延伸题目，本题中的
nums可能包含重复元素。 - 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
解法：
这个问题与 Search in Rotated Sorted Array 的区别在于此问题中存在重复元素。
由此引发的问题是，旋转之后，数组后半部分不一定小于前半部分了。因此，在使用 (nums[mid] >= nums[0]) == (target >= nums[0]) 判断 nums[mid] 和 target 是否位于同一部分时会出错。
原因在于旋转后的数组，头部和尾部元素的值可能相等。其实只需要去除数组尾部重复的元素，就能保证前半部分一定大于后半部分。
4 4 5 5 6 7 1 2 3 4 4 4 4
^
4 4 5 5 6 7 1 2 3
如此以来再使用 Search in Rotated Sorted Array 中的解法，就可以了。
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
lo = 0
hi = len(nums) - 1
inf = float('inf')
if len(nums) == 0:
return False
while hi > lo and nums[lo] == nums[hi]:
hi -= 1
while lo <= hi:
mid = lo + (hi-lo) // 2
if (nums[mid] >= nums[0]) == (target >= nums[0]):
num = nums[mid]
else:
if target < nums[0]:
num = -inf
else:
num = inf
if num == target:
return True
elif num < target:
lo = mid + 1
else:
hi = mid - 1
return False