题解 | #旋转数组的最小数字#
旋转数组的最小数字
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
由于没有转换前的数组是非递减，即右边的数字总是大于等于相邻左边的。
转换后，分两种情况：
第一种：有0个元素转换，即还是原来的数组，那么最左边的依然是最小值，因此转换后如果最左边的值小于最右边的值，说明是0个元素转换。
第二种：大于0个元素转换，那么最左边的数字一定是大于等于最右边的，那么最小值一定是在下一个元素比上一个元素小的情况下的那个下一个元素。
我们可以定义两个指针left和right，left指针从前面往后走，right指针从后面往前走，
如果left指向的元素大于下一个元素，那么最小值就是下一个元素；如果right指向的元素小于上一个元素，那么最小值就是right所值的元素。
import java.util.*;
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int left = 0;
int right = array.length - 1;
if(array[left] < array[right])
return array[left];
while(left < right){
if(array[left] > array[left+1])
return array[left+1];
else if(array[right-1] > array[right])
return array[right];
else
left++;
right--;
}
return -1;
}
}
CVTE公司福利 258人发布