드디어 내 힘으로 풀었다. 핵심적으로 사용한 것은 Bucket sort 이다.
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
이 문제의 해결을 위한 constraints
Situation
주어진 배열 nums 의 숫자 중 많이 반복된 숫자 k개 까지를 반환하라.
Task
Bucket sort
[1, 1, 1, 2, 2, 3] 과 같이 숫자 배열이 주어졌다고 가정하면 오른쪽 표와 같은 hash table을 만들 수 있다.
사실 여기까지 만드는건 이고 직관적으로 만들 수 있다.
key | value |
1 | 3번 |
2 | 2번 |
3 | 1번 |
이제 자주 반복된 k 개를 어떻게 추출해야 할까? 이 부분이 문제이다.
여기서 사용한 개념이 bucket sort 이다.
이러한 배열을 통해서 sorting을 할 것인데
1은 3번 반복 되었고, 2는 2번, 1은 1번
이 그림과 같이 index 가 찾는 값이고, array 안에 반복 횟수가 들어간다면?
첫 번째 이유는 성립이 불가능하다. contraint 를 보면 array 안에 범위는 다음과 같다.
만약 -1000 이면 index를 -1000으로 만들어야 할까? 물론 이에 알맞게 array 의 규칙을 세울 수 있겠지만 부족한 알고리즘 풀이 시간에 알맞은 결정은 아니다.
두 번째 이유는 nums 안에 담긴 수 중에서 가장 큰 값이 1,000이면 array 의 length 는 10001 이 되어야 한다.
10000 이라는 숫자가 만약 4번 나왔다고 한다면?
물론 가능은 하지만, 효율적이진 않다.
Action
그렇다면 위의 첫 번째 이유를 해결하기 위해 반복 횟수를 index 로 두는 것이다.
nums = [1, 1, 1, 1, 1, 3, 3, 4] 와 같은 배열을 hash table 을 거쳐 bucket 에 담게 되면 다음과 같다.
위의 frequent 를 index 로, 각 frequent 에 해당하는 value 를 array 에 할당한다.
마지막으로 뒤에서 부터 배열을 순회하면서 k개 만큼 배열에 담아 반환하면 정렬이 되어있다.
이 그림에서 보면 nums.length 가 8이다. 그리고 배열은 최대 index가 8이다.
nums 의 길이가 8이지만, 8번 반복된 숫자가 있다면 n 은 반드시 1 이어야 한다.
8번이나 반복되어 index = 8 에 할당되기 위해선 n 이 1이어야 하기 때문이다.
Result
알고리즘 고수 분들은 코드가 짧던데 과연 성능이 어떠할까 걱정했지만 시간 복잡도, 공간 복잡도가 나쁘지 않다.
작성한 코드는 다음과 같다.
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if (nums.length == 1 && k == 1) {
return new int[] {nums[0]};
}
int[] result = new int[k];
List<List<Integer>> bucket = new ArrayList<>();
for (int i = 0; i <= nums.length; i ++) {
bucket.add(new ArrayList<>());
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i ++) {
int cur = nums[i];
map.computeIfPresent(cur, (key, v) -> {
v += 1;
return v;
});
map.putIfAbsent(cur, 1);
}
for (int value : map.keySet()) {
int count = map.get(value);
bucket.get(count).add(value);
}
int resultIndex = 0;
int i = bucket.size();
while (resultIndex < k && i >= 0) {
i -= 1;
if (bucket.get(i).isEmpty()) {
continue;
}
for (int j = 0; j < bucket.get(i).size(); j ++) {
result[resultIndex] = bucket.get(i).get(j);
resultIndex += 1;
}
}
return result;
}
}
Java
복사
