[C++] LeetCode : Find Peak Element

Question

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

Given a 0-indexed 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] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

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

 

peak element는이웃 element 보다 큰 element이다. 

인덱스가 0인 정수 배열 nums가 주어지면 peak element를 찾고 해당 인덱스를 반환한다. 배열에 여러 peak가 포함된 경우 하나만 반환한다. 

nums[-1] = nums[n] = -∞라고 가정한다. 즉, 요소는 항상 배열 외부에 있는 element보다 큰 것으로 간주된다.

제약사항

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

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 문제를 잘 살펴보면 배열의 모든 요소를 다 검사해 봐야 할 것 같다. 만약 peak 요소가 맨 뒤에 있다면 순차 탐색으로 O(n) 일 것 같다.
• 하지만 잘 생각해보면 배열의 모든 요소를 검사해볼 필요는 없다. 일부 요소만 보고도 peak 요소를 찾아낼 수 있다.

고려사항

• 배열의 크기 형태가 어떤식으로 배치되어 있는지

---

Solution1 (Bruth Force)

문제를 단순하게 생각해보면, 아래 세 경우로 배열이 나올 수 있다.

즉 어차피 현재 원소가 다음 원소보다 크면 그 원소가 peak이라고 볼 수 있다. 
뒤죽박죽 한 경우라도 하나만 반환하면 되기 때문에 다른 경우는 고려할 필요가 없다. 

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        for(int i=0; i<nums.size()-1;i++){
        if(nums[i] > nums[i+1]){
            return i;
        }
        return nums.size()-1;
    }
};

• Time complexity : O(n) 
• Space Complexity : O(1) 

Solution2

모든 원소를 볼 필요는 없다.
binary search를 통해 탐색범위를 줄여가며 원소를 찾을 수 있다. 

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

• Time complexity : O(logN) 
• Space Complexity : O(1) 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/801/

Explore - LeetCode