未分類

Find Peak Element

Array, BinarySearch, Go, LeetCode

Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example:

In array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Note:

Your solution should be in logarithmic complexity.

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

Default:

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

解答思路:

回傳陣列中比周圍大的任一個元素位置，直接遍歷來做的話其實只要檢查每個取出的元素是否比前一個與下一個大即可，但是如果要在時間複雜度O(logn)以內的話，表示每次取出元素至少都要篩選掉一半，但是要選擇用二元搜尋又很奇怪，因為根本不是有序的資料，說起來本來就不是要尋找特定的目標，所以要如何每次都篩選掉一半以上元素就是首要目標(因為解答只要其中一種即可)，一開始就取最中間的兩個值並比較兩者大小，看是要最中間的值與其下一個值或前一個值都可以，這邊以中間與下一個值與主，如果中間值比較大，接下來只要重覆上述動作找開頭到中間值的範圍即可，反之如果下一個值比較大就是找中間下一個值到結尾的範圍，最後透過從中間逐步向外的方式篩出其中一個解答，最好的情況是山峰的位置在最中間，而最糟的情況則是在陣列的最兩側。

程式碼解說:

一開始都與普通的二元搜尋無異，只是這次比較的對象是中間與下一個值，如果中間值比較大，就將搜尋的範圍改為開頭到中間值(結尾指向的位置改到中間)，反之如果下一個值比較大就將範圍改為中間下一個值到結尾(開頭指向的位置改到中間下一個)，最後待開頭與結尾都指向同一個位置，該位置上的值就會是其中一個解答

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

完整程式碼:

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

總結:

要找出陣列中比周圍大的任一個元素位置並在時間複雜度O(logn)以內的話，由於資料不是排序加上沒有特定的目標要搜尋，因此如果選擇用二元搜尋，最主要每次取出元素都篩選掉一半就是首要目標，其做法是取最中間的兩個值並比較兩者大小(以中間與下一個值為例)，如果中間值比較大，接下來只要重覆上述動作找開頭到中間值的範圍即可，反之亦然，最後透過從中間逐步向外的方式篩出其中一個解答。

分享到