Descrition
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.
click to show spoilers.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
public int (int[] nums) { int len = nums.length; if (len == 1) { return 0; } if (len == 2) { return nums[0] > nums[1] ? 0 : 1; } if (nums[0] > nums[1]) { return 0; } if (nums[len - 1] > nums[len - 2]) { return len - 1; } for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) { return i; } } return 0; }
|
Result
AC
Analyse
这个就是简单的数据分析过程。
Optimization
First
1 2 3 4 5 6 7 8
|
public int (int[] nums) { for (int i = 1; i < nums.length; i++) { if (nums[i] < nums[i - 1]) { return i - 1; } } return nums.length - 1; }
|
Second
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
public int (int[] nums) { int low = 0; int high = nums.length - 1; while (low < high){ int mid1 = low + (high - low) / 2; int mid2 = mid1 + 1; if (nums[mid1] < nums[mid2]) { low = mid2; } else { high = mid1; } } return low; }
|
Analyse
第一种方法就是利用了本地函数的特性，只要有nums[i] < nums[i - 1]的条件出现就说明有一个peak出现了。第二种方法是二分查找来确定，这个方法不是典型的二分，因为只需要找出其中一个peak就可以了。
近期评论