难度

简单

思路

  • 二分法
    1. /**
    2. * 递增数组->截取一部分放置原数组后面。
    3. * 要点: 二分法判断。让中间数值与最右边比较，如果中间值较大，则表示最小值在右边，如果中间值较小，则表示最小值在左边。如果相等，则右值-1，继续二分法查找。
    4. */
    5. public class No11_ArrayTheminNumber {
    6.   public static void main(String[] args) {
    7.       int[] data = {3,4,5,1};
    8.       System.out.println(minArray_1(data));
    9.   }
    10.   public static int minArray_1(int[] numbers) {
    11.       if (numbers.length == 0)
    12.           return -1;
    13.       if (numbers.length == 1)
    14.           return numbers[0];
    15.       int i =0, j = numbers.length - 1;
    16.       while (j > i) {
    17.           int mid = (i + j)/2; // 取小值
    18.           if (numbers[mid] > numbers[j]) {
    19.               // 在右边,+1不要忘记了
    20.               i = mid + 1;
    21.           } else if (numbers[mid] < numbers[j]) {
    22.               // 在右边
    23.               j = mid;
    24.           } else {
    25.               // 相等
    26.               j--;
    27.           }
    28.       }
    29.       return numbers[i];
    30.   }
    31. }
    | 时间复杂度 | O(logn) | | —- | —- | | 空间复杂度 | O(1) |

总结

  • 如何确定该往哪个方法走。需要判断中间值与最右边的值的大小。
  • 在最坏的情况下，即数组中每个元素都相等，则时间复杂度会退化为 O(n)。