162. Find Peak Element c++ 문제

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.

피크 요소는 이웃보다 엄격하게 큰 요소입니다.

정수 배열 nums가 주어지면 피크 요소를 찾고 해당 인덱스를 반환합니다. 
배열에 여러 피크가 포함된 경우 인덱스를 피크 중 하나에 반환합니다.

nums[-1] = nums[n] = -∞라고 상상할 수 있습니다.

O(log n) 시간에 실행되는 알고리즘을 작성해야 합니다.

 

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.

 

Constraints: 제약

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• nums[i] != nums[i + 1] for all valid i.

peak원소의 위치를 반환하면 되는 문제이다.

그냥 쉽게 최대값을 찾으면 되지 않을까 생각했는데 You must write an algorithm that runs in O(log n) time

O(log n) 으로 풀어라는 조건이 있어 binary search 트리를 이용하여 구연해야했다.

 

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        
        int left = 0;
        int right = nums.size()-1;
    
        while(left < right )
        {
            int pivot = (left+right)/2;
            int num = nums[pivot];
            int nextNum = nums[pivot+1];
            
            if(num < nextNum)
            {
                left = pivot+1;
            }
            else
            {
                right = pivot;
            }
        }    
        return right;
    }
};

 

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie