JunyiCode
4/11/2020 - 4:12 AM

162. Find Peak Element

练习讲题

/*
O(logn) && O(1)
Note:
    binary search 
        什么时候可以while(l <= r). 当跳出条件是
            if(nums[mid] == target)
        取等号会死循环时用while(l < r)
            if (nums[mid] > nums[mid + 1])
                r = mid;
*/


public class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[mid + 1])
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
}
/*
面试时:
    1. 问清楚You may imagine that nums[-1] = nums[n] = -∞.
    2. 分cases讨论清楚
      (1) All the numbers appear in a descending order. 
      (2) All the elements appear in ascending order. 
      (3)  The peak appears somewhere in the middle. 
*/


class Solution {
    public int findPeakElement(int[] nums) {
        for(int i = 0; i < nums.length - 1; i++) {
            if(nums[i] > nums[i + 1])
                return i;
        }
        
        return nums.length - 1;
    }
}
/*
O(logn)
O(logn)
*/

public class Solution {
    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }
    public int search(int[] nums, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }
}