剑指 Offer 11. 旋转数组的最小数字

image.png

暴力法

时间复杂度：O(n)，空间复杂度：O(1)

  1. public class Solution {
  2.     // 暴力法，pre在前，number在后，当number比pre小的时候，说明到达旋转点，返回number
  3.     // 如果全程都没有到达旋转点，说明旋转点在第一个数，返回numbers[0]
  4.     public int minArray(int[] numbers) {
  5.         int pre = numbers[0];
  6.         for (int number : numbers) {
  7.             if (number < pre) return number;
  8.             pre = number;
  9.         }
  10.         return numbers[0];
  11.     }

二分法

时间复杂度：O(log n)，空间复杂度：O(1)

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 这里的作用是判断 left ~ right 之间是否是单调递增的
            // e.g1 {3,1,3,3}, d.g2 {1,3,3}
            // 如果中间值比右边大，说明不是单调递增的，所以数组有旋转过，要把 left 移到 mid 右边
            if (numbers[mid] > numbers[right]) left = mid + 1;
            // 如果中间值比左边小，说明是单调
            else if (numbers[mid] < numbers[left]) right = mid;
            else right --;
        }
        return numbers[left];
    }
}