Accepted solution with log(n) performance (40 ms) with explanation


  • 0
    Y

    Use ternary search , variation of divide and conquer algorithm, to solve it with log(n) performance.
    Select middle element and choose left or right part of array, saving invariant n[start] < n[middle] > n[end]

    int findPeakElement(const vector<int> &n) {
        int s=0, e=n.size()-1;
        while(s<e){
            int c = (e-s)/2+s;
            if(n[c]<n[c+1])
                s=c+1;
            else if ( n[c]<n[c-1])
                e=c-1;
            else return c;
        }
        return s;
    }
    

  • 0
    S
    This post is deleted!

  • 1
    R

    Your solution will not pass the [2,1] input, as n[-1] will give you outofbound exception


  • 0
    Z

    So in order to avoid out-of-bound exception, the code should be:
    (if mid=0 or last element, then it only need to be compared with its next or former element)

    int findPeakElement(const vector<int> &n) {
        int s=0, e=n.size()-1;
        while(s<=e){
            int c = (e-s)/2+s;
            if(c+1<n.size()&&n[c]<n[c+1])
                s=c+1;
            else if ( c-1>=0&&n[c]<n[c-1])
                e=c-1;
            else return c;
        }
        return s;
    }

  • 0
    L

    how about this case [1,3,2,4], from the question's condition num[-1] = num[n] = -∞, it should return 3, not 1, is that right?


  • 0
    T

    3 and 1 are both OK. As the problem says that there may be multiple peaks, returning the index of any peak is fine.


  • 0
    L

    for my understanding, the peak means the highest, so like this case [1,2,1,2,1,2,1], return 1, 3, 5 are all OK, but for [1,3,2,4], it should be return 3.


  • 0
    Z

    A peak element is an element that is greater than its neighbors. Not the highest


  • 0
    T

    @zjulyx is right.


Log in to reply
 

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