专栏首页蛮三刀的后端开发专栏[Leetcode][python]搜索旋转排序数组/搜索旋转排序数组 II

[Leetcode][python]搜索旋转排序数组/搜索旋转排序数组 II

Search in Rotated Sorted Array

题目大意

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

解题思路

二分搜索是针对有序数组而言,对于中间有次转折的有序数组,只是要多区分几种情况,二分搜索依然是适用的。 主要就是判断mid的左右哪边是中断的

代码

该解法的判断表达是对称的结构,有助于记忆

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0; right = len(nums) - 1
        while left <= right:
            mid = (left + right) / 2
            if target == nums[mid]:
                return mid
            if nums[mid] >= nums[left]:  # 中点大于最左边,说明左边区间没有混乱
                if target < nums[mid] and target >= nums[left]:  # 此时若目标数小于中间数而且大于最左边,说明就在左边区间
                    right = mid - 1
                else:  # 不然就在右边区间
                    left = mid + 1
            else:  # 中点小于最右边,说明右边区间没有混乱
                if target > nums[mid] and target <= nums[right]:  # 此时若目标数大于中间数而且小于最右边,说明就在右边区间
                    left = mid + 1
                else:  # 不然就在左边区间
                    right = mid - 1
        return -1  # 找不到

Search in Rotated Sorted Array II

题目大意

把一个有重复的排序数组进行旋转,如[0,1,1,1,2,3,4,5]旋转3位成为[3,4,5,0,1,1,1,2]。在这样的数组中判断目标数字是否存在。

解题思路

和上题其实唯一的区别在于如果重复的数字中间进行了旋转,所以只要加入

if nums[left] == nums[mid] == nums[right]:
    left += 1
    right -= 1

其他相同。

代码

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        left = 0; right = len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target: 
                return True
            if nums[left] == nums[mid] == nums[right]:  # 所有指针都一个数字,说明旋转时有的在左边有的在右边,需要往中间看
                left += 1
                right -= 1
            elif nums[mid] >= nums[left]:  # 中点大于最左边,说明左边区间没有混乱
                if target < nums[mid] and target >= nums[left]:  # 此时若目标数小于中间数而且大于最左边,说明就在左边区间
                    right = mid - 1
                else:  # 不然就在右边区间
                    left = mid + 1
            else:  # 中点小于最右边,说明右边区间没有混乱
                if target > nums[mid] and target <= nums[right]:  # 此时若目标数大于中间数而且小于最右边,说明就在右边区间
                    left = mid + 1
                else:  # 不然就在左边区间
                    right = mid - 1
        return False

总结

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Leetcode][python]Find First and Last Position of Element in Sorted Array/在排序数组中查找元素的第一个和最后一个位置

    给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

    后端技术漫谈
  • [Leetcode][python]寻找峰值

    https://leetcode-cn.com/problems/find-peak-element/description/

    后端技术漫谈
  • [Leetcode][python]Sort Colors/颜色分类

    给出一个由红、白、蓝三种颜色组成的数组,把相同颜色的元素放到一起,并整体按照红、白、蓝的顺序。用0表示红色,1表示白色,2表示蓝色。这题也称为荷兰国旗问题。

    后端技术漫谈
  • 【Leetcode】81. 搜索旋转排序数组 II

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

    Leetcode名企之路
  • LeetCode<二分搜索> 33 & 81 Search in Rotated Sorted Array I&II

    Suppose an array sorted in ascending order is rotated at some pivot unknown to y...

    大学里的混子
  • OMG,我从来没想过,二分查找还有诗?!

    二分查找是极其简单容易理解的一种算法,但它的变形与细节也是极其繁杂的,一不小心就容易踩坑。

    五分钟学算法
  • 二分查找算法细节详解

    我相信对很多读者朋友来说,编写二分查找的算法代码属于玄学编程,虽然看起来很简单,就是会出错,要么会漏个等号,要么少加个 1。

    haifeiWu
  • 基于二分搜索法的floor与ceil

    此时使用上述二分查找算法,搜索出来的index为3。那如果我想要获取最左侧等于target的index或最右侧等于target的index呢?此时上述算法失效!

    公众号guangcity
  • 二分查找算法详解

    有一天阿东到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把阿东拦下,要检查一下哪本书没有登记出借。阿东正准备把每一本书在报警器下过一下,以找出引发警...

    灵魂画师牧码
  • 二分查找算法详解

    有一天阿东到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把阿东拦下,要检查一下哪本书没有登记出借。阿东正准备把每一本书在报警器下过一下,以找出引发警...

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券