81. 搜索旋转排序数组 II [medium]
81. 搜索旋转排序数组 II [medium]
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 可能包含重复元素。
- 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
通过次数31,159 | 提交次数87,257
Second Try
2020-07-03
参考题解才想起来可以不用递归的写法，虽然时间没有明显的优势，但是代码量少了不少，思路也同样清晰。
重要的是归纳出在第一二步判断之后，只剩下nums[left] == nums[mid] == nums[right]这一种情况。其他的一边相等另一边不等的情况，都被第一二步判断概括了。
第一二步判断中比0033多了一个条件，不再只是从本侧确定有序来考虑问题，同时考虑对面是否无序的情况。
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
# 先按照普通方法判断是否能确定为有序或无序，最后如果出现相等，则left和right分别往中间走起
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return True
# 左侧有序
if nums[left] < nums[mid] or nums[mid] > nums[right]:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1 # 在另一侧中
# 右侧有序
elif nums[mid] < nums[right] or nums[left] > nums[mid]:
if nums[mid] <= target <= nums[right]:
left = mid + 1 #
else:
right = mid - 1 #在另一侧中
# 剩下的其实只有三者都相等的情况了，其他情况都被第一二步概括了
elif nums[left] == nums[mid] == nums[right]:
left += 1 # 全都往中间走一走，毕竟nums[left]与nums[right]已经不是正确答案
right -= 1
return False
- 执行用时：32 ms, 在所有 Python 提交中击败了22.77%的用户
- 内存消耗：13.2 MB, 在所有 Python 提交中击败了100.00%的用户
First Try
2020-07-03
在相等的情况下有点迷糊，敲了太多的代码，虽然思路还行，但编写耗时太多了。
因为记得上一道类似的题目0033并不需要使用递归写法，所以一开始直接写下去，写着写着发现有点头疼，太麻烦了，还是得上递归。
使用的是函数递归的方法，并且在无法确定哪边是有序数组的时候，直接无脑把两侧都扔进去了，一行代码执行两个调用，用or来确定是否返回正确的结果。
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
挂掉的情况
- [3, 1, 1], 3
- [1, 1, 3, 1], 3
"""
# 本来如果是升序唯一数组，旋转后选择总归有一次是有序的，end - start > 0, 无序的是 end - start < 0
# 现在出现另一种情况，有序的可能是end - start >= 0, 此时无序的也可能是 end - start <= 0, 混淆点在于同时等于0的情况
# 无序出现 = 0的情况下，有序的整个数组应该就是相等的，所以额外判断多一个元素看是否相等即可
if not len(nums):
return False
def bisearch(nums, left, right, target):
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
return False
def mixsearch(nums, left, right, target):
while left <= right:
mid = left + (right - left) // 2
# print(left, right, mid)
if nums[mid] == target:
return True
# 判断[mid, right]是否有序
if nums[right] - nums[mid] > 0 or nums[mid] - nums[left] < 0:
if target > nums[right] or target < nums[mid]:
return mixsearch(nums, left, mid - 1, target)
else:
return bisearch(nums, mid + 1, right, target)
# 判断[lfet, right]是否有序
elif nums[mid] - nums[left] > 0 or nums[right] - nums[mid] < 0:
if target < nums[left] or target > nums[mid]:
# 到对面半边去找
return mixsearch(nums, mid + 1, right, target)
else:
return bisearch(nums, left, mid - 1, target)
# 1. 如果无序一侧相等，则有序的一侧必定也是相等, 会造成left,mid, right三个位置相等的情况
# 2. 如果有序一侧相等，则无序一侧要么仍然无序，要么也是相等。而无序的情况已经在第一二波测试过了，剩下的依然是三个位置相等的情况
elif nums[left] == nums[mid] == nums[right]:
# return False # 又贡献了一波
# 无脑走一波就行了，反正mid并不符合，继续往下缩小就行
return mixsearch(nums, left, mid - 1, target) or mixsearch(nums, mid + 1, right, target)
# 在第一二波上提供两侧同时判断之后，没有其他情况了。
# 剩下的，肯定是一边相等的为有序（而且都等于nums[mid]，根本不需额外判断），另一边为无序(有序的已经在前面第一二个判断中剔除了)
# else:
# if nums[right] - nums[mid] < 0:
# return mixsearch(nums, mid + 1, right, target)
# elif nums[mid] - nums[left] < 0:
# print('catcha!')
# return mixsearch(nums, left, mid - 1, target)
return False
left, right = 0, len(nums) - 1
return mixsearch(nums, left, right, target)
- 执行用时：28 ms, 在所有 Python 提交中击败了42.55%的用户
- 内存消耗：12.9 MB, 在所有 Python 提交中击败了100.00%的用户