Top K Frequent Elements

먼저 개수를 셉니다. 값에서 개수로 대응하는 해시 맵을 사용해 한 번 순회하면 [4, 1, 4, 2, 1, 4, 3, 1, 4]가 4 → 4, 1 → 3, 2 → 1, 3 → 1로 바뀝니다.

그런 다음 서로 다른 값들을 답의 순서대로 배치합니다. 개수가 많은 값이 먼저 오고, 개수가 같으면 값이 작은 것이 먼저 옵니다. 정렬에는 이 비교 기준을 그대로 적용합니다. 개수를 첫 번째 키로, 값을 두 번째 키로 두면 정렬된 목록의 첫 k개 항목이 답입니다. 여기서는 순서가 4, 1, 2, 3이고, k = 2이므로 4와 1을 선택합니다.

개수를 세는 데는 O(n)이 듭니다. 서로 다른 d개의 값을 정렬하는 데는 O(d log d)가 들며, 모든 값이 서로 다르면 최대 O(n log n)입니다. 값이 10^4개라면 비교 횟수는 약 1.3 × 10^5회로, 빠른 편입니다. 낭비되는 부분은 첫 k개만 필요한데도 모든 값을 정렬한다는 점입니다.

가장 좋은 값 k개만 필요하므로 후보도 k개만 유지합니다. 새로운 값이 들어올 때마다, 보유한 후보 중 가장 약한 후보보다 나은지 확인합니다. 여기서 더 약하다는 것은 개수가 더 적거나, 개수가 같고 값이 더 큰 경우를 의미합니다. 이 규칙에 따라 정렬된 최소 힙을 사용하면 가장 약한 후보가 맨 위에 놓이므로, 이를 O(1)에 확인하고 O(log k)에 교체할 수 있습니다.

서로 다른 값들을 순회합니다. 힙에 k개보다 적은 값이 들어 있는 동안에는 값을 추가합니다. 그다음부터는 맨 위의 값보다 나은 값이 들어오면 그 값을 교체하고, 그렇지 않은 값은 버립니다. 이미 더 나은 값 k개를 유지하고 있기 때문입니다. 라이브러리 힙을 사용하면 모든 값을 힙에 넣고, 힙 크기가 k를 초과할 때마다 한 번 꺼내는 방식이 더 간단하며, 이렇게 해도 같은 k개 값이 유지됩니다.

마지막에 힙에는 정답이 들어 있지만, 정답 순서대로 정렬되어 있지는 않습니다. 힙은 부분적으로만 정렬되어 있기 때문입니다. 값을 꺼내면 가장 약한 값이 먼저 나오므로, 정답은 마지막 위치부터 첫 번째 위치까지 거꾸로 기록합니다.

서로 다른 값 d개 각각에 대해 k개 항목을 담은 힙 연산을 최대 한 번 수행하므로, 선택에는 O(d log k)가 걸립니다. k가 d보다 훨씬 작을 때는 정렬하는 것보다 빠릅니다. 예를 들어 서로 다른 값 8000개 중 상위 10개를 찾는 경우입니다.

횟수는 아무 숫자나 될 수 없습니다. n까지의 1부터 시작하는 정수입니다. 따라서 버킷 정렬을 사용할 수 있습니다. 각 횟수마다 버킷 하나를 만들고, 버킷 c에는 정확히 c번 나타나는 값들을 담은 다음, 버킷 n부터 아래로 버킷을 읽습니다. 값은 가장 자주 나오는 것부터 나오며, 횟수끼리는 비교할 필요가 없습니다.

동률 규칙에는 한 가지 조건이 더 있습니다. 버킷 안에서는 더 작은 값이 먼저 와야 합니다. 값의 범위는 -10^4부터 10^4까지이므로, R = 2 × 10^4 + 1개의 카운터로 이루어진 배열을 사용해 횟수를 셀 수 있습니다. 값 v는 인덱스 v + 10^4에 둡니다. 이 배열을 가장 작은 값부터 가장 큰 값까지 순회하며 각 값을 해당 횟수의 버킷에 추가합니다. 각 버킷은 오름차순으로 채워지므로 동률 규칙을 만족하고, 따로 정렬할 필요가 없습니다.

[5, -2, 7, -2, 7, 5, 9]의 경우 순회하면서 -2, 5, 7을 그 순서대로 버킷 2에 넣고, 9는 버킷 1에 넣습니다. 버킷 7부터 아래로 읽으면 값이 들어 있는 첫 번째 버킷은 버킷 2이며, k = 2이면 -2와 5를 선택합니다.

작업은 nums를 한 번 순회하고, R개의 카운터를 한 번 순회하며, 버킷을 한 번 순회하는 것으로, 총 O(n + R)입니다. 값의 범위가 고정되어 있으면 선형 시간입니다. 카운팅 배열 대신 해시 맵을 사용해도 횟수 세기는 선형 시간으로 유지되지만, 버킷은 맵의 순서대로 채워지므로 동률 규칙을 지키려면 각 버킷을 정렬해야 합니다.