Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* A peak element is an element that is greater than its neighbors.
- Given an input array nums, where nums[i] ≠ nums[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 nums[-1] = nums[n] = -∞.
- Example 1:
- Input: nums = [1,2,3,1]
- Output: 2
- Explanation: 3 is a peak element and your function should return the index number 2.
- Example 2:
- Input: nums = [1,2,1,3,5,6,4]
- Output: 1 or 5
- Explanation: Your function can return either index number 1 where the peak element is 2,
- or index number 5 where the peak element is 6.
- Note:
- Your solution should be in logarithmic complexity.
- */
- class Solution {
- public int findPeakElement(int[] nums) {
- if (nums.length == 0) {
- return -1;
- }
- return findHelper(nums, 0, nums.length - 1);
- }
- private int findHelper(int[] nums, int left, int right) {
- if (left > right) return - 1;
- int midIndex = left + ((right - left) / 2);
- int mid = nums[midIndex];
- int pre = midIndex == 0 ? Integer.MIN_VALUE : nums[midIndex - 1];
- int post = midIndex == nums.length - 1 ? Integer.MIN_VALUE : nums[midIndex + 1];
- if (mid > pre && mid > post || left == right) return midIndex;
- else if (mid < pre) return findHelper(nums, left, midIndex - 1);//left side has the peak
- else return findHelper(nums, midIndex + 1, right);//right side has the peak
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement