专栏首页木又AI帮打卡群刷题总结0727——搜索旋转排序数组 II

打卡群刷题总结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 False

PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

PPS:还是得日更呀,总结一下总是好的。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T162-打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    木又AI帮
  • 【leetcode刷题】20T39-颜色分类

    https://leetcode-cn.com/problems/sort-color

    木又AI帮
  • 【leetcode刷题】20T10-三数之和

    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组...

    木又AI帮
  • [算法总结] 二分查找

    二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

    尾尾部落
  • LeetCode 81. 搜索旋转排序数组 II(二分查找)

    ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

    Michael阿明
  • 漫画:知乎面试题(旋转数组最小值Ⅱ - 进阶版)

    今天是小浩算法“365刷题计划”第72天。继续为大家讲解二分法系列篇 - 旋转排序数组最小值Ⅱ(进阶版)。话不多说,直接看题:

    程序员小浩
  • 【剑指offer:和为s的两个数字】双指针

    题目描述:输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,则输出任意一对即可。

    心谭博客
  • LeetCode 15. 3Sum题目分析代码

    给出一个有n个整数的数组S,在S中找到三个整数a, b, c,找到所有使得a + b + c = 0的三元组。

    desperate633
  • LeetCode-15-3Sum

    Given an array S of n integers, are there elements a, b, c in S such that a + b ...

    欠扁的小篮子
  • [Leetcode][python]搜索旋转排序数组/搜索旋转排序数组 II

    把一个严格升序的数组进行旋转,如[0,1,2,3,4,5]旋转3位成为[3,4,5,0,1,2]。在这样的数组中找到目标数字。如果存在返回下标,不存在返回-1。...

    后端技术漫谈

扫码关注云+社区

领取腾讯云代金券