锐客网

  1. 首页 > it技术 > >

剑指offer|剑指offer 旋转数组的最小数字

算法剑指Offer

【剑指offer|剑指offer 旋转数组的最小数字】题目传送
剑指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]; } };

    推荐阅读


    上一篇：SQL|python操作mysql插入数据

    下一篇：c++|PTA堆栈—有效括号判断