未分類

Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

提示 解題應用
Array Array/Slice
BinarySearch BinarySearch

Default:

1
2
3
func findMin(nums []int) int {
}

解答思路:

建議可以先參考先前Search in Rotated Sorted Array的解法,解說較為詳細,基本上概念完全一樣,之前是先找出這些有序的資料和正確位置有序相比位移了多少(找最小值的位置做比較),接著在利用這個位移來邊做二分法等演算法找出目標位置,當然這次只是要找最小值而已,所以就只要省了一個步驟即可。

程式碼解說:

程式碼與先前的題目完全一樣甚至更簡單,因為就只是省了後頭的步驟而已,尋找最小值的方式與二元搜尋脫不了關係,不過中位數比較的值是與最後一個值相比,如果中位數比最後一個值大表示最小值被移動到後頭,此時將開頭指向的index移到中位數的下一個,而如果比最後一個值小(題目有說彼此值不會重覆,故無相等情況),就將尾巴指向的index移到中位數,記得不是移到中位數的前一個,因為我們要找的最小值也有可能是該中位數,所以也要包含在其中,最後當開頭位置超過尾巴的位置而跳開迴圈時,尾巴位置的值便是我們要的最小值

1
2
3
4
5
6
7
8
9
10
11
12
var mid int
front := 0
rear := len(nums) - 1
for front < rear {
mid = (front + rear) / 2
if nums[mid] > nums[rear] {
front = mid + 1
} else {
rear = mid
}
}
return nums[rear]

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findMin(nums []int) int {
var mid int
front := 0
rear := len(nums) - 1
for front < rear {
mid = (front + rear) / 2
if nums[mid] > nums[rear] {
front = mid + 1
} else {
rear = mid
}
}
return nums[rear]
}

總結:

建議可以先參考先前Search in Rotated Sorted Array的解法,解說較為詳細,基本上概念完全一樣,這次只是要找最小值而已,所以只要找出這些有序的資料和正確位置有序相比位移了多少(也就找最小值的位置),最後就只是把最小值所在位置的值取出而已。

分享到