153. Find Minimum in Rotated Sorted Array
題目
Suppose an array of length n sorted in ascending order is
rotated
between1
andn
times. For example, the arraynums = [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
ofunique
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];
};