对于一个有序循环数组arr,返回arr中的最小值。有序循环数组是指,有序数组左边任意长度的部分放到右边去,右边的部分拿到左边来。比如数组[1,2,3,3,4],是有序循环数组,[4,1,2,3,3]也是。
给定数组arr及它的大小n,请返回最小值。
测试样例:
[4,1,2,3,3],5
返回:1
public int getMin(int[] arr, int n) {
int left = 0;
int right = arr.length-1;
int mid=0;
while(left < right){
mid = left + (right - left)/2;
//这是判断已经被改动位置的循环数组
if(arr[mid] > arr[left]){
left = mid;//这是判断在右边最小有序
}else if(arr[mid] < arr[left]){
right = mid;//这是判断在左边最小有序
}else{
//这是left=mid的情况时
mid++;
break;
}
}
int min = arr[mid];
//还要判断一下没有改动循环数组的情况
int min_min = min>arr[0]? arr[0]:min;
return min_min;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)