面试题11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
解题1（超时）
可能是自己刷题少的原因，导致思路很少
第一个想到的思路，就是：
例如有一个数组A
1：拿到A[0]与A[A.length-1]作比较，
2：如果A[0]>=A[A.length-1]，就把这个数字想办法放在最后。
自己测试结果是对的，但是提交的时候，显示超时，思路应该是没问题的，就是笨了许多
public int minArray(int[] numbers) { Boolean bool = true; int i = 0; int j = numbers.length - 1; int tmp; while (bool){ //如果第一个比最后一个大，就交换位置 if(numbers[i] >= numbers[j]){ tmp = numbers[i]; //忘前移动数组 for (int k = 0; k < numbers.length-1; k++) { numbers[k] = numbers[k+1]; } numbers[j] = tmp; }else{ bool = false; } } return numbers[0]; }
解题2 解答
我就纳闷了，不是要求要旋转数组吗？怎么变成找最小值了。
下面这是在解答区找到的一个，很好的思路，适合当模板
static public int minArr(int[] numbers){ int i = 0, j = numbers.length - 1; while (i < j) { int m = (i + j) / 2;//拿到中间的位置 if (numbers[m] > numbers[j]){ //拿到中间的位置之后，把中间的位置和最后的位置做比较 i = m + 1; } else if (numbers[m] < numbers[j]){ j = m; } else{ j--; } } return numbers[i]; }
解题3
我也是很无奈，不是说好的旋转数组吗？
这样都能提交成功
public int minArray(int[] numbers) { Arrays.sort(numbers); return numbers[0]; }
