LintCode 75. Find Peak Element 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/find-peak-element/
There is an integer array which has the following features:
- The numbers in adjacent positions are different.
- A[0] < A[1] && A[A.length – 2] > A[A.length – 1].
We define a position P is a peek if:
A[P] > A[P-1] && A[P] > A[P+1]
Find a peak element in this array. Return the index of the peak.
Notice
The array may contains multiple peeks, find any of them.
Example
Given [1, 2, 1, 3, 4, 5, 7, 6]
Return index 1 (which is number 2) or 6 (which is number 7)
解题思路
题目是求一个数值大于相邻位置两数的峰值数位置。
题目最关键条件：第一个数和第二数是上升关系A[0] < A[1]，倒数第二个数和倒数第一个数是下降关系A[A.length - 2] > A[A.length - 1]。这个条件说明了，整个数列的变化，是先上升，后下降。那说明在整个区间中，总有一个从上升到下降的拐点，即一定会存在一个峰值。
最简单地解法就是遍历数组，只要找到一个大于两边的元素就可以了，但复杂度为O(N)。这题可以用复杂度更优化O(logN)的二分法来做。
用二分法不断缩减搜索范围找峰值。因为题目只求一个峰值，那么二分法始终会找到一个峰值。
- 如果二分法找到中间位置的数A[mid]大于相邻两位置的数，则A[mid]即为峰值。
- 如果 A[mid] < A[mid+1]，说明mid到end这段区间是一个先上升，后下降的区间，一定存在有峰值（并不是说左边就一定没有，只是说右边一定有，所以往右边走）
- 同理，A[mid] < A[mid – 1]的话，说明 start 到 mid这段区间也是先上升，后下降的区间。也能确定左边一定有峰值。
参考代码
class Solution {
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
public int findPeak(int[] A) {
if (A == null || A.length == 0) {
return -1;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) {
return mid;
} else if (A[mid] < A[mid - 1]) {
end = mid;
} else {
start = mid;
}
}
if (A[start] > A[end]) {
return start;
} else {
return end;
}
}
}