1287. Element Appearing More Than 25% In Sorted Array

https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/

내 풀이

#93ms 50.41%
class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        arrMap = {}
        sum = 0
        for i in arr:
            if(i in arrMap):
                arrMap[i] += 1
            else:
                arrMap[i] = 1
            sum += 1
        for i in arrMap:
            if(arrMap[i] * 4>sum):
                return i

모든 배열을 순회하므로 O(n)의 시간복잡도와 그 값을 map에 저장하므로 O(n)의 공간복잡도를 갖음.

다른 풀이

1. 데이터가 정렬되어 입력되는 것을 이용.

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        size = len(arr) // 4
        for i in range(len(arr) - size):
            if arr[i] == arr[i + size]:
                return arr[i]
        
        return -1

아이디어: 전체 입력의 25%초과하는 입력이기 위한 데이터의 갯수 n=len(arr)//4 처음 x라는 데이터가 i번째 인덱스에서 입력 되었을 경우, i+n번째 인덱스가 x일 경우 x는 ans인 점을 사용함
장점:
공간복잡도가 O(1)으로 메모리를 추가로 사용하지 않음.

2. 이진 탐색

from bisect import bisect_left, bisect_right 
class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        candidates = [arr[n // 4], arr[n // 2], arr[3 * n // 4]]
        target = n / 4
        
        for candidate in candidates:
            left = bisect_left(arr, candidate)
            right = bisect_right(arr, candidate) - 1
            if right - left + 1 > target:
                return candidate
            
        return -1

아이디어 ans는 전체 배열의 1/4를 초과하므로 배열의 1/4, 2/4, 3/4 지점에 적어도 하나는 들어있음.
그 세 곳의 bisect_right - bisect_left + 1은 해당 값의 갯수를 나타내므로 그 값이 target보다 크다면 해당 값이 정답이 된다.

bisect모듈의 bisect_left, bisect_right함수는 리스트와 값을 받아서 값이 있는 곳의 각각 왼쪽, 오른쪽 인덱스를 리턴한다,
만약 값이 존재하지 않는다면 들어갈 수 있는 인덱스의 오른쪽 값을 나타낸다.