剑指offer 10. 旋转数组的最小数字

【剑指offer系列题解】

【题目地址】

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1 。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为 0 ，请返回 −1 。

数据范围

数组长度 [0,90]。

样例

输入：nums = [2, 2, 2, 0, 1]

输出：0

最直接的方法就是从头往后遍历，直到前一个大于当前遍历的数字为止，当前遍历的这个元素就是最小值。

class Solution {
public:
    int findMin(vector& nums) {
        int n = nums.size();
        if (n == 0)    return -1;
        int i;
        for (i = 1; i < n; i++)
            if (nums[i - 1] > nums[i])
                return nums[i];
        return nums[0];
    }
};

下图中水平的图线代表元素相同，具体算法步骤如下：

• 如果该数组首尾元素有相同的，就先去除相同的元素，保证二分算法可以正常运行。因为我们不确定数组旋转过后首尾元素是否会出现相同的情况，为了不影响二分查找的进行，要进行去重操作，下图就是一个例子。
• 进行二分查找，找到一个临界点比 nums[0] 的元素刚好要小。

class Solution {
public:
    int findMin(vector& nums) {
        int n = nums.size() - 1;
        if (n < 0) return -1;
        while (n > 0 && nums[n] == nums[0])    n--;    //去掉数组最后与数组开头相同的部分
        if (nums[0] <= nums[n]) return nums[0]; //如果此时数组已经有序，返回第一个元素
        int l = 0, r = n;
        while (l < r)  //一直二分，直到找到临界点
        {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0])   r = mid;
            else    l = mid + 1;
        }
        return nums[r];
    }
};

欢迎大家在评论区交流~