题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素.例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为 1

题目分析

• 递增序列
• 一部分数移到后面

参数说明

/**
 * @param {number[]} numbers
 * @return {number}
 */

题解及实现

1.暴力解法

旋转后两部分都是有序的,但两部分相接处会出现突变的情况,且突变点右边就是最小值

var minArray = function (numbers) {
  let i;
  for (i = numbers.length - 1; i > 0; i--) {
    if (numbers[i - 1] > numbers[i]) break;
  }
  return numbers[i];
};

时间复杂度:O(n)遍历一遍

• 资源使用情况
  • 执行用时：80 ms, 在所有 JavaScript 提交中击败了 90.81%的用户
  • 内存消耗：39 MB, 在所有 JavaScript 提交中击败了 15.45%的用户
    问题:没有充分利用递增序列的特点

2.二分法

考虑到旋转之后,突变点右边的数都小于等于数组最后一个数,左边的数都大于等于数组最后一个数,根据此条件进行二分查找该突变点

var minArray = function (numbers) {
  let left = 0,
    right = numbers.length - 1;
  while (left < right) {
    // 二分法
    const temp = (left + right) >> 1;
    if (numbers[temp] > numbers[right]) {
      left = temp + 1;
    } else if (numbers[temp] < numbers[right]) {
      right = temp;
    } else {
      right--;
    }
  }
  return numbers[left];
};

时间复杂度:O(log(n))

• 资源使用情况
  • 执行用时：76 ms, 在所有 JavaScript 提交中击败了96.48%的用户
  • 内存消耗：39 MB, 在所有 JavaScript 提交中击败了16.20%的用户