寻找旋转排序数组中的最小值 II
假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
数组中可能存在重复的元素。
解题
暴力直接线性查找
或者，线性找到第一个开始降序的位置对应的数
应该考虑二分法
递归 + 二分
public class Solution {
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] num) {
// write your code here
if( num == null || num.length == 0)
return 0;
if(num.length == 1)
return num[0];
return findMin(num,0,num.length - 1);
}
public int findMin(int[] num,int left,int right){
if(left == right)
return num[left];
if(right == left + 1)
return Math.min(num[left],num[right]);
int mid = (left + right)/2;
if( num[right] > num[left])
return num[left];
else if( num[right] == num [left])
return findMin(num,left + 1,right);
else if(num[mid] >= num[left])
return findMin(num,mid,right);
else
return findMin(num,left,mid);
}
}
Java Code
二分
public class Solution {
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] num) {
// write your code here
if( num == null || num.length == 0)
return 0;
if(num.length == 1)
return num[0];
int low = 0;
int high = num.length -1;
int mid = low;
while(low < high){
mid = (low + high)/2;
if(num[mid] > num[high]){
low = mid + 1;
}else if( num[mid] < num[high]){
high = mid ;
}else{
high--;
}
}
return num[low];
}
}
Java Code