首页 > 代码库 > 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。