Leetcode 162) Find Peak Element

09 Sep 2021 in Algorithms

내 답안

class Solution {
    public int findPeakElement(int[] nums) {
        if(nums==null || nums.length==1){
            return 0;
        }
        int l = 0;
        int r = nums.length-1;

        while(l+1<r){
            int mid = l+(r-l)/2;
            //mid-1 이 0이상이게..
            if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1]){
                return mid;
            }else if(nums[mid]>nums[mid-1] && nums[mid] <nums[mid+1]){
                l=mid;
            }else if(nums[mid]<nums[mid-1] && nums[mid]>nums[mid+1]){
                r=mid;
            }else{
                r=mid;
            }
        }
        if(nums[0]>nums[nums.length-1]){
            return 0;
        }else{
            return nums.length-1;   
        }
    }
}

• template 3으로 짠 답안!
• while문은 원소가 최소 3개일때 돌아간다.

public class Solution {
    public int findPeakElement(int[] nums) {
        // [1,2,1,3,5,6,4]
        // -inf 1 2 1 3 5 6 4 -inf
        
         
        //peak, => nums[m+1]< nums[m] > nums[m-1] 
        
        //1. nums[m-1]< nums[m] < nums[m+1]  => increasing. right . , move our left pointer to the mid.
        //2. nums[m-1]> nums[m] > nums[m+1]  => decreasing. left, move our right pointer to the mid
        //3. nums[m-1]> nums[m] < nums[m+1] => either way works.

        //peak, => nums[m+1]< nums[m] > nums[m-1] => contain more than 3 elements => in other word, pointer l and r should be at least 2 element apart. 0,1,2 would work. 

                
        int left = 0;
        int right = nums.length-1;
        
        //if l is 0, then r should be equal and greater than 2. 
        while(left+2<=right){
            int mid = left + (right-left)/2;
            if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1]){
                return mid;
            }else if(nums[mid-1]< nums[mid] && nums[mid] < nums[mid+1]){
                left= mid; // we will be less aggressive,
                //becasue from this condition, we don't know if mid+1 is the peak or not, and it is possible. to examine this,we  don't want to blow the mid point information away.
            }else if(nums[mid-1] >nums[mid] && nums[mid] >nums[mid+1]){
                right = mid; // less aggressive, it applies the same logic.
            }else{
                right= mid;
            }
          
        }
        //out, l = a, r = a+1.
            
            //the premise here, is there is at least one peak  , ther should be the answer.
                      //l r    => this case could have happned, if this problem does not say it should contain at least one answer.            
            // -inf 1 2 3 4 5 6 -inf
            // -inf 9 8 7 6 5 3 -inf
        //we want to check which is bigger, and return bigger element.
            if(nums[right]<nums[left]){
                return left;
            }else{return right;}
        
        

    }
}

다른 답안

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < nums[mid - 1]) {
                end = mid;
            } else if (nums[mid] < nums[mid + 1]) {
                start = mid;
            } else {
                return mid;
            }
        }

        if (nums[start] < nums[end]) {
            return end;
        }
        return start; 
    }
}