剑指offer - 旋转数组的最小数字 - JavaScript

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

# 题目描述

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

本题和LeetCode154.寻找旋转排序数组中的最小值 II一样。

# 解法 1:暴力法

遍历一次,直接找到比较出最小的数字。

时间复杂度是 O(N),空间复杂度是 O(1)。

// ac地址:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2019-12-24-xuan-zhuan-shu-zu/

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function (numbers) {
  const length = numbers.length;
  if (!length) {
    return null;
  }

  return Math.min(...numbers);
};

# 解法 2: 二分查找

看到这种题目,正确做法基本上都是需要使用二分查找

对于这种变形的二分查找的考察,解决思路主要都是:观察 left、mid、right 三个指针对应的元素的大小关系,然后移动指针。

具体的解决方法主要是:多写几个例子,然后观察如何移动。

举几个例子来推导解题细节(请记住题干的数组有序、某个点旋转这两个条件):

  • arr[left] < arr[right]: 直接返回arr[left]。例如:1 2 3 4 5
  • arr[left] < arr[mid]: 说明从数组下标范围为[left, mid]的元素是递增的,此时最小值只可能出现在[mid + 1, length)范围内。例如:4 5 1 2 3
  • arr[mid] < arr[right]: 说明从数组下标范围为[mid, right]的元素是递增的,此时最小值只可能出现在[left, mid] 范围内。注意,这里不能跳过下标mid。例如:3 3 3 4 5
  • 其他情况,此时arr[mid] = arr[right] = arr[left]: 移动 left,缩小范围即可。例如:1 1 1 0 1
// ac地址:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2019-12-24-xuan-zhuan-shu-zu/

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function (numbers) {
  const length = numbers.length;
  if (!length) {
    return 0;
  }

  let left = 0,
    right = length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    // 子数组有序
    if (numbers[left] < numbers[right]) {
      return numbers[left];
    }

    // 左子数组有序,最小值在右边
    // 那么mid肯定不可能是最小值(因为numbers[mid]大于numbers[left])
    if (numbers[left] < numbers[mid]) {
      left = mid + 1;
      // 右子数组有序,最小值在左边
      // 这里right=mid因为最小值可能就是numbers[mid]
    } else if (numbers[mid] < numbers[right]) {
      right = mid;
    } else {
      // 无法判断,缩小下范围
      ++left;
    }
  }

  return numbers[left];
};

# 更多资料