leetcode [153]Find Minimum in Rotated Sorted Array

佚名 7年前 (2019-04-22) 随笔 2190人围观抢沙发百度已收录

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]).

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

题目大意：

找到旋转数组中的最小值。

解法：

按顺序寻找到数组中非递增的那个位置的数字，即是旋转数组中的最小值。

java:

class Solution {
    public int findMin(int[] nums) {
        int res=nums[0];
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]>nums[i+1]){
                res=nums[i+1];
                break;
            }
        }
        return res;
    }
}

采用二分查找寻找最小值。当数组中的第一个元素小于最后一个，说明该数组递增，直接返回第一个元素。否则查看数组中的中间元素，如果该元素比第一个元素要大的话，说明最小值在后半部分，要不然就在前半部分。

java:

class Solution {
    public int findMin(int[] nums) {
        int start=0,end=nums.length-1;
        while(start<end){
            if(nums[start]<nums[end]) break;
            int mid=(start+end)/2;
            if(nums[start]<=nums[mid]) start=mid+1;
            else end=mid;
        }
        return nums[start];
    }
}