首页 > 代码库 > LeetCode 154.Find Minimum in Rotated Sorted Array II

LeetCode 154.Find Minimum in Rotated Sorted Array II

题目:

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.

The array may contain duplicates.

思路:

1.题目中指出sorted array,find target使用二分法。

2.分为以下三种情况

(1)数组只有一个元素:nums[0]即为最小值。

(2)数组不是rotated sorted array,退化为sorted array:nums[0]即为最小值。

(3)数组是rotated sorted array:nums[start] >= nums[end]:

a:nums[mid]比左右数都小,返回nums[mid];

b:nums[mid]大于nums[start].

c:nums[mid]小于nums[end].

d:nums[mid]等于nums[end],如下图,无法判断是start移到mid还是end移到mid,故start++;

技术分享

代码:

public class Solution {
    public int findMin(int[] nums) {
        int start = 0,end = nums.length-1,mid=0;
//length equals 1;
if(nums.length == 1){ return nums[0]; }
//is rotated sorted array;
while(nums[start] >= nums[end] && start + 1 < end){ mid = start + (end - start)/2; if(nums[mid] < nums[mid+1] && nums[mid] < nums[mid-1]){ return nums[mid]; }else if(nums[mid] > nums[start]){ start = mid; }else if(nums[mid] < nums[start]){ end = mid; }else{ start++; } }
//is not a rotated sorted array;
if(nums[start] < nums[end]){ return nums[start]; } return nums[end]; } }

 

LeetCode 154.Find Minimum in Rotated Sorted Array II