8ms clear C++ solution


  • 3

    Well, this is a problem called "peak finding" and has been simplified by assuming neighbor elements in the array to be different.

    Since we need to solve it in logarithmic time complexity, binary search is a natural choice.

    The following code is actually very similar to binary search except terminating/updating conditions which have been set to fit the purpose of this problem.

    class Solution {
    public:
        bool isPeak(vector<int>& nums, int idx) {
            // Return whether nums[idx] is a peak
            if (idx > 0 && nums[idx - 1] > nums[idx])
                return false;
            if (idx < nums.size() - 1 && nums[idx + 1] > nums[idx])
                return false;
            return true;
        }
        int findPeakElement(vector<int>& nums) {
            int left = 0, right = nums.size() - 1;
            while (left < right) {
                int mid = (left & right) + ((left ^ right) >> 1);
                if (isPeak(nums, mid)) return mid; // Already find a peak, return it.
                if (mid > 0 && nums[mid - 1] > nums[mid]) right = mid - 1; // the peak is to the left of mid
                else if (mid < nums.size() - 1 && nums[mid + 1] > nums[mid]) // the peak is to the right of mid
                    left = mid + 1;
            }
            return left;
        }
    };
    

    For those who want to learn more about peak finding (the problem can be extended to higher dimension, which is then not so trivial), here is a more general discussion: http://courses.csail.mit.edu/6.006/spring11/rec/rec02.pdf


Log in to reply
 

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