剑指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, right]的元素是递增的,此时最小值只可能出现在[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];
};

更多资料

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×