当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.153.Find Minimum in Rotated Sorted Array

LeetCode.153.Find Minimum in Rotated Sorted Array


题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.


解题过程

找旋转有序数组的最小值,二分搜索。用mid和low,high比较,判断转折点也就是极值点的位置:
当a[low,…,high]是旋转升序数组时(完全有序不考虑),并且也没有重复值时:
如果a[mid]>a[low],说明左边升序,转折点在右边,最小值也在右边,也可以用a[mid]>a[high]判断
如果a[mid]<a[low],说明右边升序,转折点在左边,最小值也在左边,也可以用a[mid]<a[high]判断

思想很好理解,但里面有坑,很容易出错。当a是{2,1}这种只有2个值且倒序的数组,这时a[low]==a[mid],很容易出错,我改了好几遍才写对。

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length-1;
        while(low<=high){
            //先判断nums[low,...,high]是否升序,即无旋转
            if(nums[low] <= nums[high])
                return nums[low];
            //nums[low,...,high]不是升序
            int mid = (low+high)/2;
            if(nums[mid]>=nums[low]){//左边升序,转折点在右边,最小值也在右边
                low=mid+1;
            }else{//右边升序,转折点在左边,最小值也在左边
                high=mid;
            }
        }
        return nums[low];
    }
}

GitHub代码


上一篇 LeetCode.033.Search in Rotated Sorted Array

下一篇 Spring-基础注解

阅读
377
阅读预计2分钟
创建日期 2018-03-01
修改日期 2018-03-03
类别
百度推荐