Another simple way to approach this problem


  • -1
    B

    The basic idea is to use binary search. We know the input array is not full sorted, but don't worry, as long as we can cast off a portion of elements during each iteration/recursion and maintain the looping invariant, we are about reach the goal finally.

    In this problem, we can compare value(mid) with value(start) and value(end), if value(mid) < value(start), we know in the range of [start mid) there exist a descending trend from a higher peek to a lower ground, of course there may exist more than one peek, but one is enough. In this case, we are free to drop rest and focus on this half, notice that since value(mid) is at a lower ground, we drop it as well.

    Same thing apply to right half if value(mid) < value(end) holds because we know there is a ascending trend.

    Finally if value(mid) is somehow equal or greater then two sides value(start)/value(end), we don't know which half to throw, but we do know the two sides would not be the last two peeks, other words, there must exist another peek at the middle of array given the truth that no neighbor values are equal. So simply discard both ends this time.

    The runing time in worset case is O(n), but in most case, it's O(lgn).

    public int findPeakElement(int[] nums) {
        int s = 0, e = nums.length-1, m=0;
        while(s < e){
    		m = (s + e) / 2;
    		if(nums[m] < nums[s]) e = m-1;  // value(mid) < value(start): get left half
    		else if(nums[m] < nums[e]) s = m+1;  // value(mid) < value(end): get right half
    		else{    // value(mid) >= value(start) && value(mid) >= value(end): discard two ends
    			s++;
    			e--;
    		}
    	}
    	return e;
    }

Log in to reply
 

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