题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个升序的数组的一个旋转,输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转,该数组的最小值为 1。
数组可能包含重复项。
注意:数组内所含元素非负,若数组大小为 0,请返回 −1。
样例
输入:nums = [2, 2, 2, 0, 1]
输出:0
算法1
(遍历)
从后往前遍历
时间复杂度 $O(n)$
C++ 代码
class Solution {
public:
int findMin(vector<int>& nums) {
// ①为空,直接返回-1
if(nums.empty())
return -1;
// ②只有一个元素,返回nums[0]
if(nums.size() == 1)
return nums[0];
// ③从最后一个往前找
int i = nums.size() - 1;
while(nums[i-1] <= nums[i] && i-1 >= 0)
i--;
return nums[i];
}
};
算法2
(二分查找)
①先排除nums最后几个元素与 nums[0]相等的情况
②然后用二分查找
若mid >= nums[0],说明待找元素在数组靠右侧
若mid <= nums[0],说明待找元素还可以往mid左侧逼近
时间复杂度 $O(lnn)$
C++ 代码
class Solution {
public:
int findMin(vector<int>& nums) {
// ①nums为空
if(nums.empty())
return -1;
// ②进行 二分查找
// nums末尾的几个元素 有可能与nums[0]相等,需要先排除
int n = nums.size() - 1;
while(nums[n] == nums[0] && n >0)
n--;
// 若排除完毕后,最后一个元素 大于nums[0],则说明nums剩下的元素是递增的
if(nums[n] > nums[0])
return nums[0];
int l = 0, r = n;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= nums[0])
l = mid + 1;
else
r = mid;
}
return nums[l];
}
};