Tricky problem tricky solution !


  • 5

    This problem seems easy ..... But I can not solve it quikly .... AS I can not figure out how to

    find the refered peek element in O(logN) time.

    After seeing others' posts .... I want to say it is so tricky to analyze it ......

    We just check the mid and mid+1 element and recheck the bigger side as the bigger side will have

    the peak element for sure.

    Here is one C++ CODE:

    class Solution {
    public:
        int findPeakElement(vector<int>& nums) {
            int start=0, end=nums.size()-1;
            while(end>start){
                int mid=(start+end)/2;
                if(nums[mid] < nums[mid+1])  start=mid+1;
                else end=mid;
            }
            return start;
        }
    };
    

    Thanks to @gangan

    You can also use the brute force traversal to find the peek element.

    class Solution {
    public:
        int findPeakElement(vector<int>& nums) {
            for(int i=1; i<nums.size(); i++){
                if(nums[i]<nums[i-1])
                    return i-1;
            }
            return nums.size()-1;
        }
    };

  • 0
    A

    How about this case [2,4,5,3,6,7,8]
    Wont your algorithm fail here, or am I missing something?


  • 0
    A

    How about this case [2,4,5,3,6,7,8] Wont your algorithm fail here, or am I missing something?


  • 0
    A

    never mind , missed this in the question num[-1] = num[n] = -∞


  • 0
    A

    never mind , missed this in the question num[-1] = num[n] = -∞


  • 0
    This post is deleted!

Log in to reply
 

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