[LeetCode] 3005. Count Elements With Maximum Frequency

문제

You are given an array nums consisting of positive integers.
Return the total frequencies of elements in nums such that those elements all have the maximum frequency.
The frequency of an element is the number of occurrences of that element in the array.

양의 정수로 이루어진 배열 nums가 주어집니다. 해당 배열의 원소들 중에서 가장 빈도수가 높은 원소들의 총 빈도수를 반환해야 합니다. 여기서 원소의 빈도수란 해당 원소가 배열에서 등장하는 횟수를 의미합니다.

 

풀이

1. Count Frequency and Max Frequency

알고리즘

1. 배열을 순회하면서 각 원소들의 빈도수를 구합니다.

2. 배열을 순회하며 가장 높은 빈도수를 계산합니다.

3. 다시 배열을 순회하며 가장 높은 빈도수의 총 빈도수를 계산합니다.

def maxFrequencyElements(self, nums):
        frequencies = {}
        for i in range(len(nums)):
            if(nums[i] in frequencies):
                frequencies[nums[i]] = frequencies[nums[i]] + 1
            else:
                frequencies[nums[i]] = 1
        
        maxFrequency = 0
        for frequency in frequencies.values():
                maxFrequency = max(maxFrequency, frequency)

        result = 0
        for frequency in frequencies.values():
            if(frequency == maxFrequency):
                result += frequency

        return result

 

복잡도

• 시간 복잡도: O(n) 
• 공간 복잡도: O(n)

 

2. One-Pass Sum Max Frequencies

알고리즘

1번 알고리즘이랑 유사하지만 반복문 하나로 끝낼 수 있는 방법입니다.

차이점은 원소의 빈도수, 최대빈도수, 총빈도수를 같이 계산한다는 차이가 있습니다.

def maxFrequencyElements(self, nums):
        frequencies = {}
        result = 0
        maxFrequency = 0
        for i in range(len(nums)):
            frequencies[nums[i]] = frequencies.get(nums[i], 0) + 1

            frequency = frequencies.get(nums[i])
            if(frequency > maxFrequency):
                result = frequency
                maxFrequency = frequency
            elif(frequency == maxFrequency):
                result += frequency
        return result

 

복잡도

• 시간 복잡도: O(n) 
• 공간 복잡도: O(n)