剑指 6.查找和排序旋转数组的最小数字

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

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。最简单的为遍历整个数组，找出最小的数，不过这是最笨的办法解题主要是用二分查找，不过二分查找也有的复杂度过高的情况以下的结果时间复杂度过高：不通过

public int minNumberInRotateArray(int [] array) {
// if (array.length<=0||array==null) {
// return 0;
// }
// int end=array.length-1;
// int start=0;
// int mid=-1;
// while (start<=end) {
// mid=(start+end)/2;
// if (array[mid]>array[start]) {
// start=mid;
//
// }
// else if(array[mid]<array[start]) {
// end=mid;
//
// }
// if (end==(start+1)) {
//
// mid=start+1;
//
// }
// else if (end==start) {
//
// mid=end;
//
// }
//
//
// }
//
//
//
//
// return array[mid];}

以下为正解：

public int minNumberInRotateArray(int [] array) {

if (array.length == 0)
return 0;
int left = 0;
int right = array.length - 1;
int middle = -1;
while (array[left]>=array[right]) {
if(right-left==1){
middle = right;
break;
}
middle = left + (right - left) / 2;
if (array[middle] >= array[left]) {
left = middle;
}
if (array[middle] <= array[right]) {
right = middle;
}
}
return array[middle];
}