题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 3 , 4 , 5 , 1 , 2 {3,4,5,1,2}3,4,5,1,2 为 1 , 2 , 3 , 4 , 5 {1,2,3,4,5}1,2,3,4,5 的一个旋转，该数组的最小值为 1 11 。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为 0 00 ，请返回 − 1 −1−1 。
数据范围
数组长度 [ 0 , 90 ] [0,90][0,90] 。
样例
输入：nums = [2, 2, 2, 0, 1] 输出：0
方法一：顺序查找 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]; } };
方法二：二分 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]; } };
欢迎大家在评论区交流~
