[Algorithm] Bucket Sort + 347. Top K Frequent Elements

Bucket Sort

INPUT: 길이가 n인 리스트 (array), 키값이 균등하게 분포한다고 가정

1. 구간을 n등분한 버킷을 만든다.

2. array[i]를 인덱스가 n * array[i]인 버킷의 위치에 추가한다.

3. 각각의 버킷에 여러개의 요소가 있으면 insertion sort로 정렬한다.

 

리트코드 347. Top K Frequent Elements

- Bucket Sort를 이용한 풀이

- n이 인풋 리스트의 길이일 때, 빈도는 1에서 n까지 분포. (가장 작은 빈도수 = 1, 가장 큰 빈도수 = n)

- 빈도수는 collections.Counter()로 센다. Counter()은 소를 key로, 빈도수를 value로 가진 딕셔너리를 리턴.

 

INPUT: 숫자를 요소로 가진 리스트

1. 길이가 n+1인 버킷을 이중리스트로 만든다. n = 3이면 길이가 4인 리스트 [[], [], [], []]

2. 버킷의 인덱스 = 빈도수로 값을 넣어준다. 리스트의 인덱스 3에 있는 요소 = 인풋 리스트에 3개 존재하는 요소

3. 뒤에서부터 k개를 찾는다. 아웃풋의 순서는 상관없다고 했으니, 버킷 안의 리스트는 정렬하지 않아도 된다.

 

* max heap으로 푼 것보다 빠름

 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counts = collections.Counter(nums)
        buckets = [[] for i in range(len(nums)+1)]
        
        for key in counts.keys():
            buckets[counts[key]].append(key)
            
        result = []
        for i in range(len(nums),0,-1):
            result += buckets[i]
            
            if len(result) == k:
                return result