首页 > 编程学习 > 81. 搜索旋转排序数组 II

81. 搜索旋转排序数组 II

发布时间:2022/8/30 14:28:17
81. 搜索旋转排序数组 II
-<通过本题第一想着不就是判断是否在数组中吗?但其实不然,其复杂度为O(n)需要遍历所有
代码:
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        for i in nums:
            if i==target:
                return True
        return False
---
其次使用二分法,此题在33题搜索旋转排序数组基础上改进
现在对33题进行整理
在有序的数组中,极右可能用到二分查找的思想,其本质为减治法,每次都有一办的数据不用查看
代码:
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        left,right=0,len(nums)-1
        while left<=right:
            mid = (left+right)//2
            #python/表示整除
            #python3 / 表示不整除,需要//
            if nums[mid]==target:
                return mid
            elif nums[mid]>=nums[right]:
                if target<nums[mid] and target>=nums[left]:
                    right=mid-1
                else:
                    left=mid+1
            else:
                if nums[right]>=target and target>nums[mid]:
                    left=mid+1
                else:
                    right=mid-1
        return -1
#其时间复杂度为O(log(N))
#空间复杂度为O(1)
---
本题的难点在于重复值,而上一题则没有
class Solution(object):
    def search(self, nums, target):
        if not nums: return -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) / 2
            if nums[mid] == target:
                return True
            if nums[left] == nums[right]:
                left += 1
                continue
            if nums[mid] <= nums[right]:
                if target > nums[mid] and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if target < nums[mid] and target >= nums[left]:
                    right = mid - 1
                else:
                    left = mid + 1
        return False
---
偷巧法:
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        for i in nums:
            if i==target:
                return True
        return False

 

 
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号