[HashTable] LeetCode: 347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/

 

347. 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.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

Constraints:

• 1 <= nums.length <= 105
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

 

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

 

---

▮ 우선순위 큐

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    	freqs = collections.Counter(nums)
        
        freqs_heap = []        
        for f in freqs:
        	heapq.heappush(freqs_heap, (-freqs[f], f))
        
        top_k = list()
        for _ in range(k):
        	top_k.append(heapq.heappop(freqs_heap)[1])
       	
        return top_k

요소의 값을 키로 하는 해시 테이블을 만들어서 빈도 수를 저장한 다음

우선순위 큐를 이용해 상위 k번 만큼 추출하여 상위 k개 요소를 추출한다.

 

Queue?

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

 

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.

 

+ 힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다.

여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다.

 

파이썬에서 우선순위 큐는 힙을 활용하는 heapq 모듈을 활용한다.

힙은 key 순서대로 정렬되므로 빈도수를 key로 하고 freqs의 key를 value로 설정했다.

또한 heapq는 최소 힙만 지원하므로 value에 -을 붙여 추출할 때 value가 큰 값을 추출할 수 있도록 하였다.

 

 

▮ Pythonic

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    	return list(zip(*collections.Counter(nums).most_common(k)))[0]

 

Input: nums = [1,1,1,2,2,3], k = 2 일 때,

Counter에는 most_common()으로 빈도 수가 높은 대로 추출하는 메소드가 있다.

>>> collections.Counter(nums).most_common(k)

[(1, 3), (2, 2)]