题目:81. 搜索旋转排序数组 II
链接: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 可能包含重复元素。 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?
解题:
1、和【leetcode刷题】20T18-搜索旋转排序数组 比较类似:利用二分查找的思想,首先确定左半区间还是右半区间是有序的(由于有重复元素,当nums[mid] == nums[left]是,是不能判断哪部分区间是有序的,需要left+=1),接着判断target是否在有序区间中,是则缩小范围为有序区间内;否则缩小范围为另一半区间。
代码:
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
left, right = 0, len(nums) - 1
while left <= right:
print(left, right)
mid = (right - left) // 2 + left
if nums[mid] == target:
return True
# 不能确定那边有序
if nums[left] == nums[mid]:
left += 1
continue
# left -> mid有序
if nums[left] < nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# mid -> right有序
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return False
PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。
PPS:还是得日更呀,总结一下总是好的。