[leetCode] 1287. Element Appearing More Than 25% In Sorted Array (Python)

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.

 

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

 

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

Solution

from collections import Counter

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        answer = 0
        
        percent_25_num = int(len(arr) // 4)
        
        cnt = Counter(arr)
        
        keys = list(cnt.keys())
        
        for key in keys:
            if cnt[key] > percent_25_num:
                answer = key
                break
                
        return answer

Solution 해설

먼저 25%의 기준이 몇 개인지 arr 의 길이를 4로 나누어 줍니다.

그 다음 collections의 Counter를 활용하여 arr 속의 각각의 값들이 몇 번씩 등장하는지 카운팅 해줍니다.

그럼 각 값들이 몇 번씩 등장하는지 정보가 담겨있는 Dictionary가 생성되고 

해당 Dictionary의 키를 활용하여 반복문을 돌면서 각 값의 카운팅 값이 25%의 개수보다 더 많다면!

정답으로 return 합니다.

 

아직 여기서 정렬된 리스트를 넘겨준다는 조건을 활용하지 않아 효율이 많이 떨어집니다.

추후에 변경할 예정입니다.

SOMJANG/CODINGTEST_PRACTICE