未分類

Find Minimum in Rotated Sorted Array

Go, LeetCode

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的解法，解說較為詳細，基本上概念完全一樣，這次只是要找最小值而已，所以只要找出這些有序的資料和正確位置有序相比位移了多少(也就找最小值的位置)，最後就只是把最小值所在位置的值取出而已。

分享到