← 18주차 · 힙과 우선순위 큐
보통해시정렬힙

가장 많이 등장한 K개 원소

정수 배열 nums와 정수 k가 주어져요. 등장 횟수가 많은 순서로 상위 k개의 원소를 반환해요.

반환하는 순서는 채점에 영향을 주지 않아요. 정답이 되는 원소 집합은 항상 유일해요.

예시

예시 1
입력
nums = [1, 1, 1, 2, 2, 3], k = 2
출력
[1, 2]
설명
1이 3번, 2가 2번, 3이 1번 등장해서 상위 2개는 1과 2예요.
예시 2
입력
nums = [1], k = 1
출력
[1]

제한 사항

  • 1 ≤ nums.length ≤ 100,000
  • 1 ≤ k ≤ 서로 다른 원소의 개수
  • 정답은 유일해요.
먼저 해시맵으로 등장 횟수를 세어요. 그다음 횟수 기준 내림차순 정렬해 앞의 k개를 자르거나, 횟수를 인덱스로 쓰는 버킷 정렬로 O(n)에 뽑을 수 있어요.
javascript
function topKFrequent(nums, k) {
  const count = new Map();
  for (const n of nums) {
    count.set(n, (count.get(n) ?? 0) + 1);
  }
  return [...count.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([value]) => value);
}
이전 문제최소 힙 직접 구현
다음 문제K개 정렬 리스트 병합
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.