问题

面试题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
输入：[4,5,5,0,1,2,3]
输出：0

解答

利用二分查找算法，因为输入的数组是一个递增排序的数组的旋转，所以旋转后的数组，左边是有序的，右边也是有序的。我们的目的是找出旋转点，也就是数组中最小的元素。
利用二分查找法，

  • 当 numbers[mid] > numbers[hi]，此时旋转点位于 [mid +1, hi] 之间，lo = mid + 1
  • 当 numbers[mid] < numbers[hi]， 此时旋转点位于 [lo, mid] 之间， hi = mid （因为是从一个递增的有序数组旋转得到的）
  • 当 numbers[mid] = numbers[hi]，此时无法判断选转点位于哪个区间。所以把 hi 向前移动一位 （hi = hi - 1）。

示例代码

  1. class Solution {
  2.     public int minArray(int[] numbers) {
  3.        int lo = 0, hi = numbers.length-1;
  4.        int m = 0;
  6.        while(lo < hi){
  7.            m = lo + (hi - lo)/2;
  8.            if(numbers[m] < numbers[hi])
  9.                 hi = m;
  10.            else if(numbers[m] > numbers[hi])
  11.                 lo = m + 1;
  12.            else 
  13.                 hi = hi - 1;
  14.        } 
  15.         return numbers[lo];
  16.     }
  17. }

执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :39.8 MB, 在所有 Java 提交中击败了100.00%的用户