AcWing 22. 旋转数组的最小数字
原题链接
中等
作者:
抹
,
2021-01-16 15:09:21
,
所有人可见
,
阅读 328
怎么说呢,这题没二分过的了,(时间还一样14ms,可能数据长度不够多)
算法1
直接往后搜
C++ 代码
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.size()==0) return -1;
int x=nums[0];
for(int i=1;i<nums.size();i++)
{
if(nums[i]<x)
return nums[i];
}
return x;
}
};
算法2
二分
C++ 代码
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[n]>=nums[0]) return nums[0];
int l=0,r=n;
while(r>l)
{
int mid=r+l>>1;
if(nums[mid]<nums[0]) r=mid;
else l=mid+1;
}
return nums[r];
}
};