题解 | #旋转数组的最小数字#

旋转数组的最小数字

http://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

第三十六题 看到logn 就应该想到用二分法 找到变化的位置 也就是最小值
那么判断条件是什么? 就看middle和最右边谁大 如果说middle比右边大,
1.假设数组是这样:456123  middle是6 right是3 那么显然 变化的值在右边middle和right中间
2.假设是412345 middle是2 right是5 说明右侧是正常的递增数列 所以变化的值必定在middle左边
3.假设是65412344 middle是4,right也是4,说明答案在middle和right中间,但因为中间不知道什么位置是旋转的地方,此时不能用二分法来找,只能让右边减一,再进入循环继续判断
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        // 二分法
        int left=0,right=rotateArray.size()-1;
        int middle=0;
        while(left<right){
            middle=(left+right)/2;
            
            // 如果中间的值比右边的大 则答案在右边
            if(rotateArray[middle] > rotateArray[right] )
                left=middle+1;
            
            // 如果中间的值比右边小 则答案在左边
            else if(rotateArray[middle] < rotateArray[right])
                right=middle;
            // 如果和最右边一样 答案在middle和right中间 继续只能缩小right--
            else
                right--;
        }
        return rotateArray[left];
    }
};

题解 文章被收录于专栏

一遍做剑指offer 一边保存做题步骤 并附带详细注释哦

全部评论

相关推荐

认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
06-07 17:17
嘉兴学院 教师
心爱的idea:你孩
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务