347. Top K Frequent Elements

[fockspaces]

we can create a dictionary for recording the exists frequency for each unique elements. then we just sorted the dict by its value (frequency), then return the last two keys, which are the top k frequenct elements

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dict_freq = defaultdict(int)
        for num in nums:
            dict_freq[num] += 1
        ans = sorted(dict_freq.items(), key= lambda item : item[1])
        return [item[0] for item in ans[-k:]]

[fockspaces]

we can leverage the advantage of heap. since we only need to the top k frequenct elements, we can just pop the heap elements for k times.

time complexity: O(k * log(N)), k is the number we pop out the elements, the log(N) is the sinking process after each pop up

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dict_freq = defaultdict(int)
        heap = []
        for num in nums:
            dict_freq[num] -= 1
        for key, value in dict_freq.items():
            heappush(heap, (value, key))
        return [heappop(heap)[1] for _ in range(k)]

[fockspaces]

O(N) solution

we can use buckets sort, the index is the frequency, the value is the list that includes corresponding element that match the freq.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dict_freq = defaultdict(int)
        buckets = [[] for _ in range(len(nums) + 1)]
        for num in nums:
            dict_freq[num] += 1
        for num, freq in dict_freq.items():
            buckets[freq].append(num)
        ans = []
        for elements in reversed(buckets):
            if elements:
                ans.extend(elements)
            if len(ans) == k:
                break
        return ans