Pengjielee's blog

题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。

例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

示例 1：
输入：nums = [1,3,5]
输出：1

示例 2：
输入：nums = [2,2,2,0,1]
输出：0

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶：

这道题是寻找旋转排序数组中的最小值的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、暴力法

旋转数组，是由两个分别有序的数组组成；
根据旋转数组的性质，问题转化成寻找两个顺序数组的分界点；

步骤：

1.从下标为0的元素开始遍历；
2.每次进行比较，如果当前元素比相邻的下一个元素大，则对应的下一元素即为最小值；
3.如果查找到最后一个元素都没有出现2这种情况，则下标为0的元素为最小元素；

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > nums[i + 1]) {
      return nums[i + 1];
    }
  }
  return nums[0];
};

2、二分查找

var findMin = function (nums) {
  let left = 0,
    right = nums.length - 1;

  if (right === 0) {
    return nums[0];
  }

  while (left < right) {
    // 获取中间元素的下标
    const mid = left + Math.floor((right - left) / 2);
    //1. nums[mid] < nums[right]，说明nums[mid]是最小值右侧的元素
    //2. nums[mid] > nums[right]，说明nums[mid]是最小值左侧的元素
    if (nums[mid] < nums[right]) {
      right = mid;
    } else if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else if (nums[mid] === nums[right]) {
      right--;
    }
  }
  return nums[left];
};