154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）
154. 寻找旋转排序数组中的最小值 II - 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到： * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4] * 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1],...
什么，还有第二关 (ᵕ—ᴗ—)
思路
和上一题不一样的是，这题给出的旋转数组中可能有重复数字出现，如果用二分思路的话策略得调整一下。
推荐阅读
[程序员] 人在国外租了间房，然后房里有电脑，在国内有什么远程方案可以使用这台电脑? 主要是用 Claude 网页版和 code
推荐阅读
人在国外租了间房，然后房里有电脑，在国内有什么远程方案可以使用这台电脑? 主要是用 Claude 网页版和 code
其实我们可以每次迭代中先让左右指针先跳过相同的数字，然后再在 [l, r] 范围内进行二分，如果中间元素 \gt nums[r]，说明最小元素在右侧，缩减左边界。否则缩减右边界。
如此逼近直至左右指针相遇。
代码
class Solution {
public:
int findMin(vector<int>& nums) {
// 这回可能有重复数字了
// 其实输入规模并不大，我是不是可以直接用 min？(≖ᴗ≖ )
int n=nums.size();
int l=0,r=n-1;
int mid=-1;
while(true){
// 每次 l, r 先跳过相同的数字
while(l<r&&l<n-1&&nums[l]==nums[l+1]){
l++;
}
while(l<r&&r>0&&nums[r]==nums[r-1]){
r--;
}
// cout<<"L: "<<l<<" R: "<<r<<endl;
// 然后再二分找
mid=((l+r)>>1);
if(l==r){
// 两指针相遇则找到最小值
return nums[mid];
}
if(nums[mid]>nums[r]){
// 比区间右侧元素大则缩减左边界
l=mid+1;
}else{
r=mid;
}
}
return -1;
}
};
4 个帖子 - 3 位参与者
来源: LinuxDo 最新话题查看原文