【剑指offer系列题解】

【题目地址】

题目描述

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

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

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

数组可能包含重复项。

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

数据范围

数组长度 $[0,90]$ 。

样例

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

输出：0
1
2
3

方法一：顺序查找 O(n)

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

class Solution {
public:
    int findMin(vector<int>& 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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

方法二：二分 O(n)

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

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

class Solution {
public:
    int findMin(vector<int>& 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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

欢迎大家在评论区交流~