Recursive O(log(N)) solution - C++


  • 0
    M

    Since you only have to find any peak, if the left or right side is bigger than the current pivot, look at that half of the array for a peak since it is guaranteed there will be one on that side. This is because there is an increase in elevation detected on that side and at the very least, the end of the array is a decrease.

    int findPeakRec(const vector<int>& num, int s, int e){
        if(e-s==0) return s;
        
        int pivot = (s + e) / 2;
        int left = pivot - 1;
        int right = pivot + 1;
    
        // set left/right heights, watching for invalid indices
        if(left == -1) left = INT_MIN;
        else left = num[left];
        if(right == e + 1) right = INT_MIN;
        else right = num[right];
        
        // look for peak at pivot, or look at side with bigger value
        if(num[pivot] > left && num[pivot] > right){
            return pivot;
        }else if(right > num[pivot]){
            return findPeakRec(num, pivot + 1, e);
        }else{
            return findPeakRec(num, s, pivot - 1);
        }
    }
    
    int findPeakElement(const vector<int> &num) {
        return findPeakRec(num, 0, num.size()-1);
    }

  • 1
    D
    int findPeakElement(const vector<int> &num){
    int len = num.size();
    int low = 0;
    int high = len-1;
    
    while(low <= high){
    	int mid = (low + high)/2;
    	//设置num[mid]的左右邻居的值
    	int left,right;
    	if(mid-1 == -1)
    		left = INT_MIN;
    	else
    		left = num[mid - 1];
    	if(mid+1 == len)
    		right = INT_MIN;
    	else
    		right = num[mid+1];
    	// 判断num[mid]是否满足条件
    	if(num[mid]>left && num[mid]>right)
    		return mid;
    	else if(num[mid]>left && num[mid]<right)
    		low = mid + 1;
    	else
    		high = mid - 1;
    }
    return -1;
    

    }


  • 0
    L

    good , log 's complexity


  • 0
    C

    shake hands~


  • 0
    E
    class Solution {
    public:
        int findPeakElement(const vector<int> &num) {
            int n = num.size();
            return find(num, 0, n - 1);
        }
        
        int find(const vector<int> &num, int start, int end) {
            int mid = (start + end) / 2;
            if(mid != 0 && num[mid] < num[mid - 1])
                return find(num, 0, mid);
            else if(mid != num.size() - 1 && num[mid] < num[mid + 1])
                return find(num, mid + 1, end);
            else
                return mid;
        }
    };

Log in to reply
 

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