AcWing 22. 旋转数组的最小数字
原题链接
中等
作者:
wwwwwwwww
,
2023-08-08 22:27:51
,
所有人可见
,
阅读 99
暴力
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.size()==0) return -1;
int min=nums[0];
for(int i=1;i<nums.size();i++)
{
if(nums[i]<min) min=nums[i];
}
return min;
}
};
整数二分
class Solution {
public:
int findMin(vector<int>& nums) {
int n=nums.size()-1;
if(n<0) return -1;
while(n>0 && nums[0]==nums[n]) n--; //删除旋转后最前面和最后面相同的数 此时才满足性质分割线左边的数>=nums[0],右边的数<nums[0]
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[l];
}
};