ACM 选手图解 LeetCode 搜索旋转排序数组

简介: ACM 选手图解 LeetCode 搜索旋转排序数组

大家好呀,我是旋转蛋。


今天解决搜索旋转排序数组,用二分查找解决局部有序数组的经典问题。


话不多说,让我们来会一会它。

640.png


   LeetCode 33:搜索旋转排序数组



题意


整数数组 nums 升序排列且无重复元素。


给你从某个下标旋转后的数组 nums 和 target,如果 target 在 nums 中返回下标,否则返回 -1。


示例


输入:nums = [4,5,6,7,0,1,2], target = 0

输出:4

解释:原 nums = [0,1,2,4,5,6,7],从下标 3 旋转后变为现在的 nums = [4,5,6,7,0,1,2]


提示


数据保证 nums 在预先未知的某个下标上进行了旋转,nums 中的每个值独一无二。


  • 1 <= len(nums) <= 5000
  • -10^4 <= nums[i]、target <= 10^4

题目解析


又是一种新的题型,难度中等。


我们早就知道,二分查找必须的条件是数组有序。


刚看这题题意第一行的时候,数数组 nums 升序排列且无重复元,当时我就默默的掏出了我的二分查找板子。


辣鸡,写的这么明显,当我是傻子嘛。

640.jpg

然后还没开心到高潮,发现 nums 被人扭了一下,旋转了。


小丑竟是我自己...


出题人你出来,你当数组是尼玛魔方嘛,想扭就扭。

640.jpg


不过再定睛一看,这题二分查找还是可解。


因为数组被旋转以后,总有一部分是有序的


比如 [4,5,6,7,0,1,2] 中,我找到 mid,不管是 0 ~ mid 或者 mid ~ n-1,总有半拉子是有序的,我们在有序的那边进行二分查找是可以的。


那这样二分查找稍微变一下,加个有序的判断,这道题的解法就出来了:


  • 找出 mid,如果 nums[mid] == target,直接返回。
  • 如果 [low,mid-1] 有序:
  • target 在 [nums[low],nums[mid]] 中,范围缩小至 [low,mid-1]。
  • target 不在 [nums[low],nums[mid]] 中,范围缩小至 [mid+1,high]。
  • 如果 [mid+1,high] 有序:
  • target 在 [nums[mid+1],nums[high]] 中,范围缩小至 [mid+1,high]。
  • target 不在 [nums[mid+1],nums[high]] 中,范围缩小至 [low,mid-1]。

下面我们来看图解。


图解


nums = [4,5,6,7,0,1,2], target = 0 为例。


首先初始化 low 和 high 指针。

640.png

low, high = 0, len(nums) - 1

第 1 步,low = 0,high = 6,mid = low + (high - low) // 2 = 3:

640.png

mid = low + (high - low) // 2


此时 nums[low] < nums[mid],且 target 不在左区间内,所以 low 向右移动至 mid + 1 = 4。

640.png

# 如果左区间有序
if nums[low] <= nums[mid]:
    # target 在左区间
    if nums[low] <= target < nums[mid]:
        high = mid - 1
    # target 在右区间
    else:
        low = mid + 1


第 2 步,low = 4,high = 6,mid = low + (high - low) // 2 = 5:

640.png


此时 nums[low] < nums[mid],且 target 在左区间内,所以 high 向左移动至 mid - 1 = 4。

640.png


第 3 步,low = 4,high = 4,mid = low + (high - low) // 2 = 4:

640.png


此时 nums[mid] == target ,直接返回结果。

# 如果找到,返回结果
if nums[mid] == target:
    return mid


本题解使用二分查找,时间复杂度为 O(n)


同时只额外维护了几个指针,所以空间复杂度为 O(1)


代码实现


Python 代码实现

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + (high - low) // 2
            # 如果找到,返回结果
            if nums[mid] == target:
                return mid
            # 如果左区间有序
            if nums[low] <= nums[mid]:
                # target 在左区间
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                # target 在右区间
                else:
                    low = mid + 1
            # 如果右区间有序
            else:
                # target 在右区间
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                # target 在左区间
                else:
                    high = mid - 1
        return -1


Java 代码实现

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } 
                else {
                    l = mid + 1;
                }
            } 
            else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } 
                else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

图解搜索旋转排序数组到这就结束辣,又是一种新的题型,你学废了嘛?

640.jpg


还是那句话,二分查找,只要每次做题小心点,就没啥问题。


如果还有什么问题的话,可以留言区提出来。


记得帮本蛋三连,点赞 + 在看 + 转发


我是帅蛋,我们下次见!



相关文章
|
2月前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
15 2
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
20 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
16 0
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
69 0
|
2月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
18 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
59 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
121 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
36 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口