《剑指offer第二版》面试题11:旋转数组的最小数字(java
2020-03-08 本文已影响0人
castlet
题目描述
把一个数组最开始的的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1.
解题思路:
- 数组可以分为两个递增数组A和B,则第二个递增数组B里的所有数字都小于等于第一个递增数组A里的数字。B的开头即为最小数字。
- 采用二分查找的方式。用三个变量分别表示数组的开头,中间和结尾。
- 如果中间数字大于等于开头数字,则说明中间数字在递增数组A里,最小数字一定在中间数字之后。
- 再对中间数字之后的数字进行二分查找即可。
代码
int min(int[] arr){
if (arr == null || arr.length == 0) {
return -1;
}
int startIndex = 0;
int endIndex = arr.length - 1;
int middleIndex = startIndex;
// 如果开头数字小于结尾数字,说明递增数组并没有旋转,第一个数字就是最小数字。
if (arr[startIndex] < arr[endIndex]) {
return arr[startIndex];
}
while(startIndex < endIndex) {
if (endIndex - startIndex == 1) {
return arr[endIndex];
}
middleIndex = startIndex + (endIndex - startIndex) / 2;
if (arr[startIndex] == arr[endIndex] && arr[startIndex] == arr[middleIndex]) {
// 三个值相等的话,采用顺序查找的方式
int min = arr[startIndex];
for (int i = startIndex; i <= endIndex; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
if (arr[middleIndex] >= arr[startIndex]) {
// middleIndex对应的数字在前面的递增数组里,则最小值在middleIndex之后
startIndex = middleIndex;
} else if (arr[middleIndex] < arr[endIndex]) {
endIndex = middleIndex ;
}
}
return -1;
}