「LeetCode每日一题」—— 33. 搜索旋转排序数组
33. 搜索旋转排序数组
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
难度:中等
题目
点击原文链接跳转查看题目
思路
这个题要求时间复杂度是O(log n),那指向的是二分查找。
如果我们先不考虑时间复杂度的要求,那我们可以通过库函数来做这个题,直接使用index来确定位置,代码见暴力方案。
现在我们考虑二分查找。
我们可以先计算mid,然后判断mid是在有序还是无序的部分。
如果mid<start,那mid在右边有序的部分
如果mid>=start,那mid在左边有序部分
如: [4,5,6,7,0,1,2] mid = 7
因为4 < 7,那 mid 左边一定有序。
mid = 7 > target,target < start,那target 不会在左边有序的部分,这一部分就可以丢掉,继续在右边查找。
代码见二分查找方案。
方案代码
暴力方案:
class Solution:
def search(self, nums: List[int], target: int) -> int:
try:
return nums.index(target)
except ValueError:
return -1
二分查找:
class Solution:
def search(self, nums: List[int], target: int) -> int:
"""用二分法,先判断左右两边哪一边是有序的,再判断是否在有序的列表之内"""
if len(nums) <= 0:
return -1
left = 0
right = len(nums) - 1
while left < right:
mid = (right - left) // 2 + left
if nums[mid] == target:
return mid
# 如果中间的值大于最左边的值,说明左边有序
if nums[mid] > nums[left]:
if nums[left] <= target <= nums[mid]:
right = mid
else:
# 这里 +1,因为上面是 <= 符号
left = mid + 1
# 否则右边有序
else:
# 注意:这里必须是 mid+1,因为根据我们的比较方式,mid属于左边的序列
if nums[mid+1] <= target <= nums[right]:
left = mid + 1
else:
right = mid
return left if nums[left] == target else -1
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/356.html
您必须登录才能发表评论。