Top-K Frequency
전체 정렬 대신 크기 K 최소 힙만 유지한다
값별 빈도를 한 번 센 뒤 후보를 힙에 넣습니다. 힙 크기가 K를 넘으면 루트, 즉 현재 후보 중 가장 낮은 빈도를 버립니다.
유지할 후보 수
K = 2
후보는 항상 2개 이하
1. Map으로 빈도 계산
2. 후보 힙은 상위 K만 남김
(1, 3)root: 최저 빈도
(3, 4)상위 후보
<= K
pop 대상
(2, 2)
(4, 1)
countfreq[value]를 먼저 만든다.
push(count, value)를 힙에 넣는다.
limitsize > K면 root를 제거한다.
output남은 후보만 빈도순으로 낸다.
결과
전체 U개 정렬보다 U log K 유지가 핵심입니다.
3: 4
1: 3