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

admin管理员组

文章数量:1794759

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

一、题目描述

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

二、题目解析

本题也是典型的自身数组顺序不是有序，但是仍然去寻找二段性去解决。

我们根据旋转数组的特性去抽象数据的范围如下：

我们要求的最小值就是C点，上图明显给我们二段性的提示，我们比较的基准就是D点。

这样我们就可以套入二分的模板去解决。

三、原码

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int len = nums.size();
        int right = len-1;
        int mid = 0;
        while(left < right)
        {
            mid = left + (right-left)/2;
            if(nums[mid] < nums[len-1])//将数组的最后一个元素作为参考值
                right = mid;
            else
                left = mid+1;
        }
        return nums[left];
    }
};

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent 删除前往查看排序设计数据数组算法

本文标签： 寻找旋转排序数组中的最小值