Paste_Image.png
My code:
public class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
if (nums.length == 1)
return 0;
return findPeakElement(0, nums.length - 1, nums);
}
private int findPeakElement(int begin, int end, int[] nums) {
if (begin == end)
return begin;
else if (begin == end - 1) {
if (nums[begin] > nums[end])
return begin;
else
return end;
}
int mid = (begin + end) / 2;
if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])
return mid;
else if (nums[mid] < nums[mid - 1])
return findPeakElement(begin, mid - 1, nums);
else
return findPeakElement(mid + 1, end, nums);
}
}
My test result:
Paste_Image.png
这次题目感觉毫无意义啊。。。虽然没有做出来。
就是要找一个峰值，而且不是唯一的。你找出来有什么意义呢。。。又不是最大的。
然后看了网上的解释写了出来。可以参加下面这一篇文章。
http://siddontang.gitbooks.io/leetcode-solution/content/array/find_peak_element.html
Paste_Image.png
**
总结： Array 凡是涉及到搜索的，而且要求复杂度是 log n 的， 一般都会涉及到， Binary Search!!!!!
**
Anyway, Good luck, Richardo!
写出了 O(N) 的解法。
My code:
public class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] > nums[i + 1])
continue;
else {
return i + 1;
}
}
return 0;
}
}
然后没想出 log (n) 的解法。看了提示，自己写了如下。
My code:
public class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
if (nums.length == 1)
return 0;
int begin = 0;
int end = nums.length - 1;
while (begin <= end) {
int middle = begin + (end - begin) / 2;
if (middle == 0) {
if (nums[0] > nums[1])
return 0;
else
return 1;
}
if (middle == nums.length - 1) {
if (nums[nums.length - 1] > nums[nums.length - 2])
return nums.length - 1;
else
return nums.length - 2;
}
if (nums[middle] > nums[middle - 1] && nums[middle] > nums[middle + 1]) {
return middle;
}
else if (nums[middle] < nums[middle - 1])
end = middle - 1;
else
begin = middle + 1;
}
return -1;
}
}
烦就烦在处理边界条件时需要分类讨论。没什么意思。
Anyway, Good luck, Richardo!
写出了 O(n) 的解法，但远没有我之前的解法漂亮。。。
连我自己都忘了这些代码，完全忘了。。。
然后开始考虑 O(log n) 解法，也是完全忘了。。。
public class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int begin = 0;
int end = nums.length - 1;
while (begin <= end) {
int middle = begin + (end - begin) / 2;
if (middle == begin) {
return nums[begin] > nums[end] ? begin : end;
}
else if (nums[middle] > nums[middle - 1] && nums[middle] > nums[middle + 1]) {
return middle;
}
else if (nums[middle] > nums[middle - 1]) {
begin = middle;
}
else {
end = middle;
}
}
return -1;
}
}
看了解释后还是比较快的写了出来。
先走到中间，middle
然后，
如果 middle == begin
这说明，该数组只有1个或两个元素，就单独处理。
否则，如果该数组，或，[begin, end] 涵盖的这段数组，一定含有至少3个元素。那么就和middle - 1, middle + 1比较。
然后处理起来就很方便了。
Anyway, Good luck, Richardo!
