[DSA][Array & Hashing] 05. Top K Frequent Elements

LeetCode 347

 

05. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements.
You may return the answer in any order.

 

 

[질문하기]

- 빈도가 같은 요소가 여러 개 있는 경우 모두 반환해야 하나요?

- 배열에 음수도 포함될 수 있나요? YES

 

 

[아이디어]

- 정렬

- Heap

- Bucket Sort

 

 

[풀이 1] Hash with Sorting

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 1. 빈도 hash 생성
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)
        
        # 2. 오름 차순 정렬
        arr = []
        for num, cnt in count.items():
            arr.append([cnt, num])
        arr.sort()

        # 3. TOP K append
        res = []
        while len(res) < k:
            res.append(arr.pop()[1])
        
        return res

빈도수를 센 후에 빈도수를 기준으로 정렬을 하고, 빈도 높은 수를 k개만큼 담는다.

 

⏱️ 시간복잡도

배열을 정렬하기 때문에 시간 복잡도는 O(nlogn)이다.

🧠 공간복잡도

배열의 원소 개수만큼의 공간이 필요하므로 공간 복잡도는 O(n)이다.

 

 

[풀이 2] Heap

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 1. 빈도 hash 생성
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)
        
        # 2. heap
        heap = []
        for num, cnt in count.items():
            heapq.heappush(heap, (cnt, num))
            if len(heap) > k: # 공간 최적화
                heapq.heappop(heap)

        # 3. TOP K append
        res = []
        while len(res) < k:
            res.append(heapq.heappop(heap)[1])
        
        return res

빈도 수를 센 후에, 정렬을 하는 대신 min-heap을 만들어서 k개의 원소만 담는다. min-heap에서 k개가 넘어가면 pop 하기 때문에 가장 작은 원소부터 pop 되어 큰 원소만 k개 남는다.

 

⏱️ 시간복잡도

빈도 수 맵의 n개의 원소에 대해 heappush 및 heappop을 하는데, heap의 크기가 최대 k이므로 각 연산의 시간 복잡도는 O(logk)이다. 따라서 전체 시간 복잡도는 O(nlogk)이다.

🧠 공간복잡도

배열의 원소 개수 + heap에서 k만큼의 공간이 필요하므로 공간 복잡도는 O(n + k)이다.

 

 

[풀이 3] Bucket Sort

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 1. 빈도 hash 생성
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        # 2. cnt번 등장한 num을 저장
        freq = [[] for i in range(len(nums) + 1)]
        for num, cnt in count.items():
            freq[cnt].append(num)

        # 3. TOP K append
        res = []
        for i in range(len(freq) - 1, 0, -1):
            for num in freq[i]:
                res.append(num)
                if len(res) == k:
                    return res

Bucket Sort는 빈도의 범위가 제한되어 있을 때 사용할 수 있다.

이 문제에서 nums의 길이가 n이면 어떤 원소도 최대 n번까지만 등장할 수 있으므로 빈도의 범위가 생긴다.

 

⏱️ 시간복잡도

배열을 한 번 순회하면서 Counter를 만들고, 빈도수를 인덱스로 하여 새로운 배열을 만들기 때문에 빈도수가 높은 (뒤에서부터) 숫자부터 차례대로 k만큼 담기 때문에 시간 복잡도는 O(n)이다.

🧠 공간복잡도

배열의 원소 개수만큼의 공간이 필요하므로 공간 복잡도는 O(n)이다.