347. Top K Frequent Elements (Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect)

링크 - https://leetcode.com/problems/top-k-frequent-elements/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Heap & Hashtable

Heap을 사용하면 가장 많이 나오는 k개의 원소들을 tracking할 수 있다. 원소들의 frequency는 hashtable를 사용한다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        heap = []
        hash_table = defaultdict(int)

        for num in nums:
            hash_table[num] += 1

        for key, val in hash_table.items():
            heapq.heappush(heap, (val, key))
            if len(heap) > k:
                heapq.heappop(heap)

        ans = []
        for val, key in heap:
            ans.append(key)
        return ans

Time Complexity: O(n + nlogk) 첫번째 n은 hash_table에 frequency를 저장할 때 발생하고, 두번째 nlogk는 heap에 k개의 가장 많이 나오는 원소들을 tracking할때 발생한다.

Space Complexity: O(n + k) n은 hash_table, k는 heap에 사용되는 공간이다.

2) Track Frequency

우리는 list에 있는 frequncy의 크기가 list의 길이보다 더 많을 수 없다는것을 알고있다. 따라서 frequncy list를 만들어서 각 frequency에 해당되는 index에 num을 집어 넣으면 된다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_counter = Counter(nums)

        freq = [[] for _ in range(len(nums) + 1)]
        for num, f in num_counter.items():
            freq[f].append(num)

        ans = []
        for i in range(len(freq) - 1, -1, -1):
            for num in freq[i]:
                ans.append(num)
                print(ans, len(ans), k)
                if len(ans) == k:
                    return ans

Time Complexity: O(n) linear time

Space Complexity: O(n) counter & freq