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];
};

參考資料