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

打卡群2刷题总结1003——搜索旋转排序数组


leetcode第33题:搜索旋转排序数组

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/


【题目】

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

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

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
    
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

【思路】

1、暴力解法:for循环遍历,找到目标值。

2、二分查找特殊变形。必须理解到:不管怎么旋转,总有一部分区间是有序的。比如,l->mid和mid->r之中至少有一个是有序的。我们的逻辑就是:判断target是否在有序区间中,在则将另一个指针移动到有序区间内,否则将有序区间的指针(除mid外的另一个边界指针)移动到有序区间外。

【代码】

python版本

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            
            # mid->r是有序的
            if nums[mid] < nums[r]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
                    
            # l->mid是有序的
            else:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
        return -1

【相似题目】

81. 搜索旋转排序数组 II

解题方法:和本题类似,如果nums[mid]和nums[r]相等,则r前移。

153. 寻找旋转排序数组中的最小值

解题方法:nums[mid]>nums[r],则l指针后移;否则r指针前移。

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

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

原始发表时间:2020-10-04

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0727——搜索旋转排序数组 II

    链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

    木又AI帮
  • 【leetcode刷题】20T18-搜索旋转排序数组

    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

    木又AI帮
  • 【leetcode刷题】T12-搜索旋转排序数组II

    今天分享leetcode第12篇文章,也是leetcode第81题—搜索旋转排序数组II(Search in Rotated Sorted Array II),...

    木又AI帮
  • 打卡群2刷题总结1002——搜索插入位置

    https://leetcode-cn.com/problems/search-insert-position/

    木又AI帮
  • ​LeetCode刷题实战33:搜索旋转排序数组

    https://www.cnblogs.com/techflow/p/12441002.html

    程序IT圈
  • ​LeetCode刷题实战81:搜索旋转排序数组 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 打卡群2刷题总结1013——不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    木又AI帮
  • (Leetcode 2021 刷题计划) 81. 搜索旋转排序数组 II

    在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+...

    windism
  • 打卡群2刷题总结1001——两数之和 II - 输入有序数组

    https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

    木又AI帮
  • 打卡群刷题总结0726——删除排序数组中的重复项 II

    链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii

    木又AI帮
  • 打卡群刷题总结0611——区域和检索-数组不可变

    链接:https://leetcode-cn.com/problems/range-sum-query-immutable

    木又AI帮
  • 杭电OJ刷题指南

    说起来刷题,很多大牛都会推荐LeetCode或者牛客网,这两个网站是刷题的好网站。但对新手来说,有一点难度,新手建议先去杭电OJ刷题,这里的题目难度不大,如果你...

    Jasonangel
  • 数据结构算法操作试题(C++/Python)——搜索旋转排序数组

    数据结构算法操作试题(C++/Python):数据结构算法操作试题(C++/Python)——目录

    莫斯
  • 【刷题】2020最新剑指Offer汇总

    新手村 关卡1-1 洛谷的第一个任务 P1000 超级玛丽游戏:点击这里 P1001 A+B Problem:点击这里 P1421 小玉买文具:点击这里...

    瑞新
  • 力扣 (LeetCode)-对称二叉树,树|刷题打卡

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • 剑指Offer系列刷题笔记汇总

    版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 ...

    Jack_Cui
  • LeetCode1-100题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到100道题了。今天把发布的1-100篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • LeetCode1-120题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到120道题了。今天把发布的1-120篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • Day68:剑指Offer总结

      本人花了两个月时间刷完了牛客网带上的剑指Offer,一共67题。本人是从4月21日开始刷题,每天一题,截止到7月6日已经全部刷完。这67题均是考察的数据结构...

    一计之长

扫码关注云+社区

领取腾讯云代金券