347. Top K Frequent Elements

Top K Frequent Elements - LeetCode

1. Using Counter

from typing import *
from collections import Counter


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter_dict = Counter()
        for num in nums:
            counter_dict[num] += 1
        return list(map(lambda x: x[0], counter_dict.most_common(k)))[:k]

Python의 HashMap인 Dictionary 자료구조를 응용한 Counter 자료구조를 이용해 풀어보았다.

 

2. Bucket Sort

from typing import *
from collections import defaultdict


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dict1 = defaultdict(int)
        for num in nums:
            dict1[num] += 1

        bucket = []
        for _ in range(len(nums) + 1):
            bucket.append([])
        for key in dict1:
            value = dict1[key]
            if not bucket[value]:
                bucket[value] = [key]
            else:
                bucket[value].append(key)

        result = []
        for i in range(len(nums), -1, -1):
            if bucket[i]:
                result += bucket[i]
                if len(result) >= k:
                    break
        return result

Counter를 사용했을 때 보다 속도도 느리고 메모리 사용량도 높다.

하지만 위에 건 Python에서 지원하는 자료구조여서 빠른 거고, 이런 정렬 방법도 있다는 것은 알아두면 좋을 것 같다.