2023-08-07力扣今日七题-好题-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-08-07力扣今日七题-好题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接：

剑指 Offer 11. 旋转数组的最小数字

154. 寻找旋转排序数组中的最小值 II

题意：

找一个数组里的最小值，这个数组是有非递减数组旋转而来的，旋转n次表示把前n个数移动到数组末尾

解：

很有趣的二分，由于是非递减数组旋转而来，所以最小值往右一定小于等于最小值左侧，可以以此进行二分

如果这个数字大于nums[r]，那么他一定属于最小值左侧，小于nums[r]一定属于右侧

But：唯一要注意等于的情况，因为存在重复数字，所以有可能所有/大部分数字都是同一个，则时候无法判断在最小值左侧还是右侧，只能减小右端点。也不能和左端点比较/增大左端点，因为有可能是旋转n次转回了原数组（前面一段一个是个非递减序列，一开始的L=0算是前面一段的最小值）

一边是Easy一边是Hard是吧，真有你的嗷leetcode（大概是暴力能过的原因=-=）

实际代码：

#include<bits/stdc++.h>
using namespace std;
int findMin(vector<int>& numbers)
{
    int lg=numbers.size(),l=0,r=lg-1;
    while(l<r)
    {
        int mid=l+((r-l)>>1);
        if(numbers[mid]==numbers[r]) r--;
        else if(numbers[mid]<numbers[r]) r=mid;
        else l=mid+1;
    }
    return numbers[l];
}
int minArray(vector<int>& numbers)
{
    int lg=numbers.size(),l=0,r=lg-1;
    while(l<r)
    {
        int mid=l+((r-l)>>1);
        if(numbers[mid]==numbers[r]) r--;
        else if(numbers[mid]<numbers[r]) r=mid;
        else l=mid+1;
    }
    return numbers[l];
}
int main()
{
    vector<int> numbers;int num;
    while(cin>>num) numbers.push_back(num);
    int ans=minArray(numbers);
    cout<<ans<<endl;
    return 0;
}

限制：文章来源地址https://www.toymoban.com/news/detail-631785.html