Two simple solutions(O(logN),O(N))


  • 0
    Q
    public int findPeakElement(int[] nums) {
        //O(logN)
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while(l <= r){
            int m = (l + r) / 2;
            // if not peek, go higher direction
            if ((m == n - 1) || (nums[m] > nums[m + 1])) {
                if ((m == 0) || (nums[m - 1] < nums[m])) return m;
                else r = m - 1;
            }
            else l = m + 1;
        }
        return 0;
    }
    public int findPeakElement2(int[] nums) {
        // O(n) solution
        int n = nums.length;
        for (int i = 0; i < n - 1; i++){
            if (nums[i] > nums[i + 1]) return i;
        }
        return n - 1;
    }

  • 0
    A
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.