Log(n) solution / 8 ms


  • -1
    P
    int findPeakElement(const vector<int> &num) {
        int n = num.size();
        // check first element & last element
        if (n == 1 || num[0] > num[1]) {
            return 0;
        } else if (num[n-1] > num[n-2]) {
            return n-1;
        }
        
        int l = 1;
        int h = n-2;
        while(l < h) {
            int mid = (l+h)/2;
            if (num[mid] > num[mid-1] && num[mid] > num[mid+1]) {
                return mid;
            } else if (num[mid] < num[mid+1]) {
                l = mid+1;
            } else {
                h = mid-1;
            }
        }
    }

  • 0
    L

    I think the answer is incorrect and OJ gives a wrong accept.
    For example the vector below: 0, 1, 2, 3, 4, 5, 4;
    l = 1; h = 5; finally, l = 4, h = 5 and mid = 4, the loop set l = 4 and next loop exit without returning a value.


  • 0
    P

    I disagree. Please look carefully, the loop sets l = 5 and not 4 in the last iteration.


  • 0
    L

    yeah, sorry that the last loop sets l = 5 and exits without returning a value. Seems there should be return l; after the while loop.


  • 1
    B

    What if the num = [1, 2, 1]?

    In this case, n = 3 and it will run to "int l = 1". Here l = 1 and h = 1, it will not enter the while loop.

    I think you should add a return at the last of this function.


  • 0
    P

    I think if Iust change my condition to if (l <= h) would fix this case.


  • 0
    Y

    amazing idea!


Log in to reply
 

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