寻找旋转排序数组中的最小值-ii

题目

这个题是 153.寻找旋转排序数组中的最小值 的扩展版, 也就是旋转数组中的元素可重复.

示例

输入: [2, 2, 3, 0, 2, 2]

输出: 0

题解

比起第 153 题, 这里需要关注 nums[mid] 跟 nums[right] 相等的情况, 因为在 [mid, right] 的这个小区间里, 右边的数字一定大于等于左边的, 因此 nums[mid] 跟 nums[right] 相等时, right = right - 1 即可.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    const mid = Math.floor((left + right) / 2)

    if (nums[mid] > nums[right]) {
      left = mid + 1
    } else if (nums[mid] < nums[right]) {
      right = mid
    } else {
      right -= 1 // 关键: 处理重复元素的情况
    }
  }
  return nums[left]
}