1287. Element Appearing More Than 25% In Sorted Array

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.

만약 arr = [1,2,2,6,6,6,6,7,10] 이런 식으로 주어질 경우가 있다고 보자. 그럼 6이 4번 출현 했음으로 리스트의 길이인 9/4 = 2...를 초과하는 경우임으로 6을 return 한다.

처음에는 뒤로 순서대로 가면서 len(arr)//4에 > count 인 경우에 break하면 되는 줄로 알았는데 뭔가 잘 안되서 익숙한 hash_table에 저장해서 for 문을 전체를 돈 다음에 sort해 준 결과를 return 하는 방식으로 문제를 sol했다.

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        # hash_table table len/4 over break
        l = len(arr)
        if l == 1:
            return arr[0]
        
        hash_table = {}
        for i in arr:
            if i not in hash_table:
                hash_table[i] = 1
            else:
                hash_table[i] += 1

        hash_table = sorted(hash_table.items(), key = lambda x : x[1], reverse=True)
        return hash_table[0][0]

이렇게 하면 결국 $O(n)$의 시간복잡도를 가진다. sorting은 $O(n log(n)$의 시간복잡도를 가지는 것으로 알고 있는데, 엄청나게 많은 시간은 걸리지 않는 것으로 보인다. 역시 hash table이 최고다.