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.------------------------------------------------------------
class Solution { public: int findPeakElement(const vector<int> &num) { if (num[0] > num[1]) return 0; if (num[num.size() - 1] > num[num.size() - 2]) return num.size() - 1; int left = 1, right = num.size() - 2; while (left <= right) { int mid = right + (left - right) / 2; if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) { return mid; }else if (num[mid] > num[mid + 1]) { right = mid - 1; }else { left = mid + 1; } } return num.size() - 1; } };
Java, updated on Oct-10th-2018
1. left < right 保证了mid + 1时不用对mid做boundry check
2. right = mid, 因为此时[mid] > [mid + 1], mid还算是一个candidate
3. ToDo: 二分法的一种写法是不设base case,然后由while里的条件来结束,最后返回left。https://shibaili.blogspot.com/2018/10/658-find-k-closest-elements.html 第2个方法用了类似的方法
class Solution { public int findPeakElement(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = (left + right) / 2; if (nums[mid] < nums[mid + 1]) { left = mid + 1; }else { right = mid; } } return left; } }
No comments:
Post a Comment