打卡群刷题总结0727——搜索旋转排序数组 II
题目：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 FalsePS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。
PPS：还是得日更呀，总结一下总是好的。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-07-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读