LeetCode 162.Find Peak Element

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.

 

 

 

풀이

 

문제를 보고 for문으로 돌면서 두번쨰인자부터 최대 길이 -1 의 인덱스까지 for문으로 돌면서 앞뒤의 인덱스를 확인하면 되는거 아니야? 라고 생각하고 쉬운문제라고 생각했었지만, You must write an algorithm that runs in O(log n) time. 

O(Iog n)의 시간복잡도를 가져야된다고한다.

 

리스트를 탐색하는데 O(Iog n)의 시간복잡도?  -> 이진탐색을 써야하는구나 

 

class Solution(object):
    def findPeakElement(self, nums):
        if len(nums)<1:
            return 0
        left =0
        right = len(nums)-1
        while left<right-1: #왼쪽 포인터가 오른쪽 포인터를 넘는 순간 while문 중지
            mid = (left+right)/2 #중간값을 기준으로 양 옆 비교 조건 만족시 return 
            if nums[mid] >nums[mid+1] and nums[mid]<nums[mid-1]:
                return mid
            if nums[mid]<nums[mid+1]: #본인 인덱스 앞쪽이 본인의 수보다 크다면 왼쪽조건 충족
                left = mid+1
            else:
                right =mid-1 
        return left

다른 사람의 코드

 

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        low, high = 0, len(nums)-1
        while low < high:
            mid = low + int((high-low)/2)
            if nums[mid] < nums[mid+1]:
                low = mid+1
            else:
                high = mid
        return low

동일한 로직이다 ,2개의 포인터로 중간값을 정하고 각 값의 조건을 충족하면 포인터가 움직인다.