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

【2种解法】【剑指Offer】【JavaScript题解】

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为 1。

NOTE：给出的所有元素都大于 0，若数组大小为 0，请返回 0。

专注前端与算法的系列干货分享，欢迎关注(¬‿¬)：
「微信公众号：心谭博客」| xxoo521.com | GitHub

解法 1:暴力法

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

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

// 原文地址：https://xxoo521.com/2019-12-24-xuan-zhuan-shu-zu/
// ac地址：https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

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

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

解法 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

// 原文地址：https://xxoo521.com/2019-12-24-xuan-zhuan-shu-zu/
// ac地址：https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

function minNumberInRotateArray(rotateArray) {
    const length = rotateArray.length;
    if (!length) {
        return 0;
    }

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

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

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

    return rotateArray[left];
}