Problem
Integer 배열이 주어졌을 때 가장 많이 나타나는 k 개의 요소를 리턴하는 문제입니다.
단, 시간복잡도가 O(n log n) 보다 빨라야 합니다.
Solution
1. Bucket Sort
첫 번째 풀이 방법은 Bucket Sort 를 활용하여 O(n) 에 구하는 방법입니다.
먼저 HashMap (number, count) 을 이용해서 각 숫자의 갯수를 전부 구합니다.
그리고 이번에는 2차원 배열 (코드에서는 List[]) 에 각 카운트 별로 해당되는 숫자를 전부 집어넣습니다.
예를 들면 [1, 1, 1, 1, 2, 2, 3, 4] 가 주어지면 아래와 같이 값이 들어갑니다.
list[0] = null
list[1] = [3, 4] // 3, 4 는 한번만 나옴
list[2] = [2]
list[3] = null
list[4] = [1]
카운트가 없는 숫자의 인덱스는 null 이 되므로 list 를 거꾸로 순회하면서 null 이 아닌 숫자들을 k 개 만큼 집어넣으면 답을 구할 수 있습니다.
2. Priority Queue
두 번째 풀이 방법은 우선순위 큐를 활용하여 O(n log k) 에 구하는 방법입니다.
1번 풀이와 마찬가지로 HashMap 에 각 숫자의 갯수를 전부 구해둡니다.
그 뒤 value 가 작은 순서대로 나오도록 우선순위 큐에 조건을 걸고, map 에 있는 값들을 전부 넣어줍니다.
대신 이 때 단순히 넣어주기만 하면 시간복잡도가 O(log n) 이지만, pq 의 사이즈가 k 를 넘지않도록 유지한다면 우선순위 큐에 삽입하는 작업은 O(log k) 가 됩니다.
어차피 k 개의 숫자 외엔 필요 없으므로 pq 의 사이즈가 k 를 초과할 때마다 가장 작은 값을 하나씩 빼주면서 진행하면 됩니다.
Java Code
// 1. Use Bucket Sort
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
List<Integer>[] bucket = new List[nums.length + 1];
for (Integer key : map.keySet()) {
int count = map.get(key);
if (bucket[count] == null) {
bucket[count] = new ArrayList<>();
}
bucket[count].add(key);
}
List<Integer> list = new ArrayList<>();
for (int i = bucket.length - 1; i >= 0 && list.size() < k; i--) {
if (bucket[i] == null) continue;
list.addAll(bucket[i]);
}
// list to array
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = list.get(i);
}
return res;
}
}
// 2. Use Priority Queue
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
Queue<Integer> pq = new PriorityQueue<>(
(a, b) -> map.get(b) - map.get(a)
);
for (Integer num : map.keySet()) {
pq.add(num);
if (pq.size() > k) {
pq.poll();
}
}
// list to array
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = pq.poll();
}
return res;
}
}
