响应式网站移动端排名,河南省建设工程质量协会网站,广东建设网 四川是什么网站,物流网站建设网链接#xff1a;
剑指 Offer 11. 旋转数组的最小数字
154. 寻找旋转排序数组中的最小值 II
题意#xff1a;
找一个数组里的最小值#xff0c;这个数组是有非递减数组旋转而来的#xff0c;旋转n次表示把前n个数移动到数组末尾
解#xff1a;
很有趣的二分#xff…链接
剑指 Offer 11. 旋转数组的最小数字
154. 寻找旋转排序数组中的最小值 II
题意
找一个数组里的最小值这个数组是有非递减数组旋转而来的旋转n次表示把前n个数移动到数组末尾
解
很有趣的二分由于是非递减数组旋转而来所以最小值往右一定小于等于最小值左侧可以以此进行二分
如果这个数字大于nums[r]那么他一定属于最小值左侧小于nums[r]一定属于右侧
But唯一要注意等于的情况因为存在重复数字所以有可能 所有/大部分数字都是同一个则时候无法判断在最小值左侧还是右侧只能减小右端点。也不能和左端点比较/增大左端点因为有可能是旋转n次转回了原数组前面一段一个是个非递减序列一开始的L0算是前面一段的最小值
一边是Easy一边是Hard是吧真有你的嗷leetcode大概是暴力能过的原因-
实际代码
#includebits/stdc.h
using namespace std;
int findMin(vectorint numbers)
{int lgnumbers.size(),l0,rlg-1;while(lr){int midl((r-l)1);if(numbers[mid]numbers[r]) r--;else if(numbers[mid]numbers[r]) rmid;else lmid1;}return numbers[l];
}
int minArray(vectorint numbers)
{int lgnumbers.size(),l0,rlg-1;while(lr){int midl((r-l)1);if(numbers[mid]numbers[r]) r--;else if(numbers[mid]numbers[r]) rmid;else lmid1;}return numbers[l];
}
int main()
{vectorint numbers;int num;while(cinnum) numbers.push_back(num);int ansminArray(numbers);coutansendl;return 0;
}限制
n numbers.length1 n 5000-5000 numbers[i] 5000numbers 原来是一个升序排序的数组并进行了 1 至 n 次旋转
