[Leetcode][Java] 162 Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index.

If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

 

"peak"는 양 옆의 숫자들보다 큰 경우를 말한다.

integer 배열 nums가 주어진다, 해당 배열에서 peak을 찾고 그 인덱스를 반환하라.

만약 배열에 여러게의 peak이 존재한다면, 어떠한 인덱스를 반환해도 된다.

배열 밖의 범위의 요소는 가장 작은 수로 인지하라 ( 즉, 맨 처음, 맨 뒤 인덱스의 값은 바로 옆 하나의 이웃보다 크면 peak이 된다)

반드시 시간 복잡도가 O(log n) 인 알고리즘을 작성하라.

 

---

배열의 search 알고리즘 문제의 시간 복잡도가 O(log n) 를 만족하기 위해서는 Binary Search를 사용해야 한다. 

결국 peak은 배열의 가장 큰 숫자를 찾으면 된다. 가장 크기 때문에 양옆의 숫자들보다 크기 때문이다.

배열의 가장 큰 숫자를 binary search로 찾는 문제로 생각하고 풀어보자.

 

    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (right > left) { // binary search 
            int pivot = (left + right) / 2;
            if (nums[pivot] < nums[pivot + 1]) {
                left = pivot + 1;
            } else {
                right = pivot;
            }
        }
        return right;
    }

 

문제출처 : 

https://leetcode.com/problems/find-peak-element/

Find Peak Element - LeetCode