【剑指offer|剑指offer 旋转数组的最小数字】题目传送
文章图片
暴力跑和二分。
这里的二分需要思考一下，
他虽然打乱了顺序，但是一样的可以二分。
有三种情况：
情况1，arr[mid] > arr[r]：4 5 6 1 2 3
arr[mid] 为 6， arr[r]为右端点 3
都是这种类似的情况，最小值的区间一定在[mid,r]
情况2，arr[mid] < arr[r]:5 6 1 2 3 4
arr[mid] 为 1， arr[r]为右端点 4
同理，最小值的区间一定在[l,mid]
情况3，arr[mid] == arr[r]:
如果是 1 0 1 1 1， arr[mid] = arr[r]= 1, 显然答案在左边
如果是 1 1 1 0 1, arr[mid] = arr[r]= 1, 显然答案在右边
所以这种情况，不能确定答案在左边还是右边，那么就让r= r- 1,慢慢缩少区间，同时也不会错过答案。
class Solution {
public:
int minNumberInRotateArray(vector rotateArray) {
int l = 0,r = rotateArray.size()-1;
while(l < r){
int mid = (l+r)/2;
if(rotateArray[mid] < rotateArray[r]){
r = mid;
}
else if(rotateArray[mid] > rotateArray[r]){
l = mid+1;
}
else{
r--;
}
}
return rotateArray[l];
}
};
推荐阅读
- c++|PTA堆栈—有效括号判断
- CSE 11 COVID Genomic
- codeforce|Codeforces Round #774 (Div. 2) D. Weight the Tree
- CUMTOJ|内部收益率（二分）
- codeforces|Codeforces Round #774 (Div. 2) A-D
- 业界观点|深度学习崛起十年（“开挂”的OpenAI革新者）
- STAC51数据分析
- 算法测试探索与实践
- 蓝桥真题|【蓝桥真题五】带三百人训练了十天精选蓝桥真题，看看他们都练些什么（三门语言题解）