[LeetCode] - M - Find Peak Element

https://leetcode.com/problems/find-peak-element/description/?envType=study-plan-v2&envId=top-interview-150

Find Peak Element - LeetCode

 

 

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

 

nums에서 양 옆의 값이 자신의 숫자보다 낮은 값들을 가진 값의 인덱스를 반환하는 문제인데,

 

문제 유형이 Binary Search이면서, 문제에서 O(log n)으로 해결하라고 되어있었음. 

 

처음엔 정렬이 안되어있는데 어떻게 Binary Search를 이용하며, 정렬을 하게되면 최소 O(n) 이나 O(n log n)으로 복잡도가 O(log n)을 넘게 되어서 어떻게 푸는지 상상이 안갔는데,

 

O(log n)으로 풀려면 Binary Search 밖에 떠오르지 않아서, 계속 생각해보니 정렬을 할 필요가 없는 문제였다.

 

mid 값을 잡고 mid값 , mid+1 값을 비교해서 start가 end보다 커질 때 start값을 반환하면 정답이다.

 

📌 -  풀이

1. start와 end를 잡고 nums[mid] < nums[mid +1] 이면 start를 mid +1 해주고 아니라면 end = mid 해주면서 start와 end를 좁혀서 start 값 반환

 

코드로 보면 되게 단순한데, 정렬을 할수 없는 상태에서 Binary Search를 한다는 것이 기본적인 개념과 달라서 조금 헤맸던 것 같다.

 

🔥 - Java 코드

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