154.寻找旋转排序数组中的最小值II

链接：154.寻找旋转排序数组中的最小值II
难度：Hard
标签：数组、二分查找
简介：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。请找出其中最小的元素。

题解 1 - typescript

• 编辑时间：2020-07-22
• 执行用时：84ms
• 内存消耗：38MB
• 编程语言：typescript
• 解法介绍：二分查找。

function findMin(numbers: number[]): number {
  let last = numbers.length - 1;
  const firstNum = numbers[0];
  while (firstNum === numbers[last] && last !== 0) {
    numbers.pop();
    last--;
  }
  if (firstNum < numbers[last]) return firstNum;
  else if (last === 0) return firstNum;
  else return _find(0, last);
  function _find(l: number, r: number): number {
    // console.log(`[find],l=${l},r=${r}`);
    if (l === r) return numbers[l];
    const mid = (l + r) >> 1;
    const num = numbers[mid];
    return num >= firstNum ? _find(mid + 1, r) : _find(l, mid);
  }
}

题解 2 - typescript

• 编辑时间：2021-04-09
• 执行用时：92ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：直接利用 Math。

function findMin(nums: number[]): number {
  return Math.min.apply({}, nums);
}

题解 3 - typescript

• 编辑时间：2021-04-09
• 执行用时：96ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：如果相等时排除右侧端点。

function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = ~~((left + right) / 2);
    if (nums[mid] < nums[right]) {
      right = mid;
    } else if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right--;
    }
  }
  return nums[left];
}