153. Find Minimum in Rotated Sorted Array

Leetcode 问题: 153. Find Minimum in Rotated Sorted Array
Categories:
Tags:

题目

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.

[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

传入一个 数字阵列 nums，所有的数字都是唯一不会重複的，这个数字阵列的数字是从小到大递增排序，但阵列会被旋转 n 次

数字阵列 nums 1 2 3 4 5
旋转 1 次 5 1 2 3 4
旋转 2 次 4 5 1 2 3
旋转 3 次 3 4 5 1 2
旋转 4 次 2 3 4 5 1
旋转 5 次 1 2 3 4 5

当旋转到第 n 次会恢復原状，每次会旋转几次不一定，尝试找出数字阵列 nums中最小的整数

Example

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

演算法

1. 二分法切割要检查的数字索引范围

设定左右指标，匡选检查的范围

  • 左边指标: 0，数字阵列最左方索引
  • 右边指标: 数字阵列最右方索引，全部的版本号数字

取左右指标索引，左右逼近到可能出现的最接近的数字，如果「左边数字索引」与「右边数字索引」没有相交，表示还可以再寻找

将数字索引位置切割成一半，拿左右字母索引的平均数当作切割点，可以把数字切割成一半，减少要检查的范围

2.「中间指标数字」与「右指标数字」比较

状况 A. 如果「中间指标数字」小于等于「右指标数字」

表示「右边」的数字序列是较大的序列

要找最小的数字需要往「左边」找

将「右指标」设定为目前的「中间指标」，再继续检查

状况 B. 如果「中间指标数字」大于「右指标数字」

表示「左边」的数字序列是较大的序列

要找最小的数字需要往「右边」找

将「左指标」设定为目前的「中间指标」，再继续检查

3. 确认最小数字在左指标

因为「左指标」会不断地往右移动，然后一直确保「左指标」的左边一定是较大的数字

所以最后左指标指定的数字，为最小的数字

答案

JavaScript

function findMin(numberList) {
    // 左指标
    var leftPointer = 0;
    // 右指标
    var rightPointer = numberList.length - 1;
    while (leftPointer < rightPointer) {
        // 当「左指标」还没超过「右指标」，表示还没比完，可以继续比较
        // 将检查的指标切半，用「中间指标」当作参考指标
        var middlePointer = leftPointer + Math.floor((rightPointer - leftPointer) / 2);
        // 「中间指标」的数字
        var middleNumber = numberList[middlePointer];
        // 「右指标」的数字
        var rightNumber = numberList[rightPointer];
        // 「中间指标数字」与「右指标数字」比较
        if (middleNumber <= rightNumber) {
            // 如果「中间指标数字」小于等于「右指标数字」，表示「右边」的数字序列是较大的序列
            // 要找最小的数字需要往「左边」找
            // 将「右指标」设定为目前的「中间指标」，再继续检查
            rightPointer = middlePointer;
        }
        else {
            // 如果「中间指标数字」大于「右指标数字」，表示「左边」的数字序列是较大的序列
            // 要找最小的数字需要往「右边」找
            // 将「左指标」设定为目前的「中间指标」，再继续检查
            leftPointer = middlePointer + 1;
        }
    }
    // 因为「左指标」会不断地往右移动，然后一直确保「左指标」的左边一定是较大的数字
    // 所以最后左指标指定的数字，为最小的数字
    return numberList[leftPointer];
}

TypeScript

function findMin(numberList: number[]): number {
    // 左指标
    let leftPointer: number = 0;
    // 右指标
    let rightPointer: number = numberList.length - 1;

    while (leftPointer < rightPointer) {
        // 当「左指标」还没超过「右指标」，表示还没比完，可以继续比较
        // 将检查的指标切半，用「中间指标」当作参考指标
        let middlePointer = leftPointer + Math.floor((rightPointer - leftPointer) / 2);

        // 「中间指标」的数字
        let middleNumber: number = numberList[middlePointer];
        // 「右指标」的数字
        let rightNumber: number = numberList[rightPointer];

        // 「中间指标数字」与「右指标数字」比较
        if (middleNumber <= rightNumber) {
            // 如果「中间指标数字」小于等于「右指标数字」，表示「右边」的数字序列是较大的序列
            // 要找最小的数字需要往「左边」找
            // 将「右指标」设定为目前的「中间指标」，再继续检查
            rightPointer = middlePointer;
        } else {
            // 如果「中间指标数字」大于「右指标数字」，表示「左边」的数字序列是较大的序列
            // 要找最小的数字需要往「右边」找
            // 将「左指标」设定为目前的「中间指标」，再继续检查
            leftPointer = middlePointer + 1;
        }
    }

    // 因为「左指标」会不断地往右移动，然后一直确保「左指标」的左边一定是较大的数字
    // 所以最后左指标指定的数字，为最小的数字
    return numberList[leftPointer];
};

参考资料