[LeetCode] Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description/

Given an integer array nums and an integer k, return the k most frequent elements.

You may return the answer in any order.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

 

Example 2:

Input: nums = [1], k = 1

Output: [1]

 

Example 3:

Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2

Output: [1,2]

 

Constraints:

• 1 <= nums.length <= 105
• -10^4 <= nums[i] <= 10^4
• k is in the range [1, the number of unique elements in the array].

• It is guaranteed that the answer is unique.

---

Given an array of numbers and a number k,

the task is to return an array containing the top k most frequently appearing numbers in the input array.

The order of the returned numbers does not matter.

Any order is accepted as long as the correct numbers are included.

숫자로 이루어진 배열과 숫자 k에 대해서, 배열 내에 가장 빈번하게 등장하는 상위 k개의 숫자를 구해서 배열로 리턴하는 문제.

배열에 들어가는 숫자는 순서 상관없이 어떤 것이든 답으로 인정한다.

 

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 숫자별로 몇 번이나 나오는지 기록이 필요하고 정렬도 필요함
        Map numsMap = new HashMap<Integer, Integer>();
        for (int n:nums) {
            if (numsMap.containsKey(n)) {
                numsMap.put(n, (int)numsMap.get(n) + 1);
            } else {
                numsMap.put(n, 1);
            }
        }
        int[] result = new int[k];
        
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(numsMap.entrySet());
        list.sort((a, b) -> b.getValue() - a.getValue());
        for(int i=0; i<k; i++){
            result[i] = list.get(i).getKey();
        }

        return result;
    }
}

 

A simple approach is to iterate through the array, count the occurrences using a Map,

convert the entrySet to a list, sort it, and then extract the top k entries.

간단하게 일단 처음부터 끝까지 숫자를 세어서 Map에 담은 후,

entryList를 생성해서 정렬하고 거기서 상위 k개를 추출해서 리턴했다.

 

“EntryList” is not an actual data structure.
It refers to a common pattern where you convert a Map’s entrySet into a List so you can sort or index through it.
This makes Maps easier to work with when you need ordering or indexed access, though it’s unclear how often this is needed in real-world applications.

EntryList라는 이름의 자료 구조가 따로 존재하는 건 아니고,

Map의 entrySet을 List로 바꿔서 정렬하거나 조회하기 위한 패턴의 하나다.

정렬, index 접근 등의 기능을 제공하기 때문에 Map을 다룰 때 편해진다. 실무에서 쓸 일이 있을지는 잘 모르겠지만.

 

Since this solution relies entirely on Java’s built-in utilities,

it felt somewhat unsatisfying, so I looked up a model answer known for having top 1% runtime performance.

아무튼 그냥 자바 내장함수를 써서 풀어냈기 때문에,

영 찝찝해서 상위 1%의 런타임을 자랑하는 모범 답안을 또 훔쳐와 봤다.

class Solution {
    static {
        int[] nums = {1, 1, 2, 2, 3};
        for (int i = 0; i < 200; i++) {
            topKFrequent(nums, 2);
        }
    }
    public static int[] topKFrequent(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        int[] freq = new int[max - min + 1];
        int max_freq = 0;
        for (int num : nums) {
            int dif = num - min;
            int f = ++freq[dif];
            if (f > max_freq) {
                max_freq = f;
            }
        }
        ArrayList<Integer>[] freqAr = new ArrayList[max_freq];
        for (int i = 0; i < freq.length; i++) {
            int n = freq[i] -1;
            if (n == -1) {
                continue;
            }
            if (freqAr[n] == null) {
                freqAr[n] = new ArrayList<Integer>();
            }
            freqAr[n].add(i + min);
        }
        int[] res = new int[k];
        int t = 0;
        for (int i = max_freq - 1; i >= 0; i--) {
            if (freqAr[i] == null) continue;
            for (int j = 0; j < freqAr[i].size(); j++) {
                res[t++] = freqAr[i].get(j);
                if (t == k) {
                    return res;
                }
            }
        } 
        return res;
    }
}

 

To put it simply,

the solution first iterates through all the numbers in the array once to find the maximum and minimum values.

Then, based on that range, it creates an int[] array called freq, which stores how many times each number appears.
During this process, it also tracks the highest frequency, which is later used as the basis for sorting by frequency.

The solution uses a sorting method called Bucket Sort.
After organizing the numbers by their frequencies,

it extracts the top k numbers starting from the highest frequency and returns them.

간단하게 설명하면, 숫자 배열 내에 존재하는 모든 숫자를 한 번 돌아서 최대값과 최소값을 구한다.

그리고 그 값의 범위에 맞춰 freq 라는 int[] 배열을 만들고, 각 숫자가 몇 번 등장했는지를 거기에 저장한다.

이 과정에서 최대 빈도수를 함께 저장해 두고, 나중에는 빈도 수 정렬을 위한 기준으로 삼는다.

Bucket Sort라는 정렬방법을 사용했는데.. 그렇게 정렬한 후에 상위부터 k개를 뽑아내고 리턴하는 식이다~_~

 

I actually thought of using this approach at first,

but I assumed it would become inefficient as the array grew larger or as k increased, so I decided not to use it.

But for this problem, it turned out to be the more efficient method after all.

For more information about Bucket Sort, refer to the link below!

https://en.wikipedia.org/wiki/Bucket_sort

나도 처음에 이런 방식을 떠올렸는데,...

아무래도 배열의 길이가 길어지거나 k가 커질수록 비효율적일 것 같아서 말았었다.

근데 아무튼 이 문제에 한해서는 그게 훨씬 효율적이었던 셈이다ㅋㅋ