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.

遍历法

思路

遍历数组, 如果一个数大于他的左右两边, 那么就是peak element

复杂度

时间O(n) 空间 O(1)

代码

public int findPeakElement(int[] nums) {    if (nums == null || nums.length == 0) {        return -1;    }    if (nums.length == 1) {        return 0;    }    for (int i = 0; i < nums.length; i++) {        if (i == 0 && nums[i] > nums[i + 1]) {            return i;        }        if (i == nums.length - 1 && nums[i - 1] < nums[i]) {            return i;        }        if ( i > 0 && i < nums.length - 1 && nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {            return i;        }    }    return - 1;}

二分法

思路

如果一个数小于他左边的数说明正在下坡, peak element在左边; 如果小于右边的数说明正在上坡, peak 在右边. 另外一种情况就是它即不小于左边也不小于右边, 此时本身就是peak element

复杂度

时间O(logn) 空间O(1)

代码

public int findPeakElement(int[] nums) {    int left = 0, right = nums.length - 1;    while (left + 1 < right) {        int mid = left + (right - left) / 2;        if (nums[mid] < nums[mid - 1]) {            right = mid;        } else if (nums[mid] < nums[mid + 1]) {            left = mid;        } else {            return mid;        }    }    if (nums[left] > nums[right]) {        return left;    } else {        return right;    }}