[LeetCode] Top K Frequent Elements

문제 :

비워있지 않은 정수형 배열이 주어질 때, 가장 빈번하게 나오는 요소들인 K를 반환하시오

 

조건

• k가 항상 유효하다고 가정 할 수 있습니다. 1 ≤ k ≤ 고유 요소 수입니다.
• 알고리즘의 시간 복잡도는 O (n log n)보다 나아야합니다. 여기서 n은 배열의 크기입니다.
• 답이 고유하다는 것이 보장됩니다. 즉, 상위 k 개의 빈번한 요소 집합이 고유합니다.
• 어떤 순서로든 답변을 반환 할 수 있습니다.

pseudo-code

요구사항 
nums배열에서 가장 빈번한 elements를 k개만큼 int[]로 반환하시오

int[] result = new int[k] 초기화
nums 배열 순회
순회 중 가장 빈번한 수를 저장
가장 빈번한 수 인지 순회중 비교
result에 빈번한 수 저장
순회 종료
result 반환

 

1차 시도 (계수정렬 시도 -> max값 조건 잘못 줌)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 계수정렬을 위한 배열 
        int[] counterArr = new int[11];
        int max = 0;
        int[] temp;
        
        //nums 순회
        for(int i = 0; i < nums.length; i++)
        {
            counterArr[nums[i]] += 1;
        }
        // O(N)?
        
        for(int i = 0; i<counterArr.length; i++)
        {
            if(max < counterArr[i])
            {
                max = i;
            }
        }
        if(max == k) {
            temp = new int[]{max};
        }
        else{
           temp = new int[]{max, k};
        }
        
        return temp;
    }
}

 

2차시도 (Example 1은 통과하나 [-1,-1]이라는 테스트케이스에서 막힘 -> 계수정렬은 양의 정수값만 가능 계수정렬불가)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 계수정렬을 위한 배열 
        int[] counterArr = new int[10000];
        int max = 0;
        int maxValue = 0;
        int[] temp;
        
        
        if(nums.length == 1) 
        {
            temp = new int[]{k};
            return temp;
        }
        else
        {
            //nums 순회
            for(int i = 0; i < nums.length; i++)
            {
                counterArr[nums[i]] += 1; // 여기서 에러 outbounds
            }
            // O(N)?

            for(int i = 0; i<counterArr.length; i++)
            {
                if(max < counterArr[i])
                {
                    max = counterArr[i];
                    maxValue = i;
                }
            }

            if(maxValue == k) 
            {
                temp = new int[]{maxValue};
            }
            else
            {
               temp = new int[]{maxValue, k};
            }

            return temp;
        }
    }
}

문제 조건을 잘못 생각함

k만큼의 길이의 int[]을 리턴해야 했음

---

Discuss 참조

 

좋아요가 가장 많은 풀이

https://leetcode.com/problems/top-k-frequent-elements/discuss/81635/3-Java-Solution-using-Array-MaxHeap-TreeMap

// use an array to save numbers into different bucket whose index is the frequency
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }
        
        // corner case: if there is only one number in nums, we need the bucket has index 1.
        List<Integer>[] bucket = new List[nums.length+1];
        for(int n:map.keySet()){
            int freq = map.get(n);
            if(bucket[freq]==null)
                bucket[freq] = new LinkedList<>();
            bucket[freq].add(n);
        }
        
        List<Integer> res = new LinkedList<>();
        for(int i=bucket.length-1; i>0 && k>0; --i){
            if(bucket[i]!=null){
                List<Integer> list = bucket[i]; 
                res.addAll(list);
                k-= list.size();
            }
        }
        
        return res;
    }
}



// use maxHeap. Put entry into maxHeap so we can always poll a number with largest frequency
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }
           
        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = 
                         new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            maxHeap.add(entry);
        }
        
        List<Integer> res = new ArrayList<>();
        while(res.size()<k){
            Map.Entry<Integer, Integer> entry = maxHeap.poll();
            res.add(entry.getKey());
        }
        return res;
    }
}

public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
            new PriorityQueue<>((a, b) -> Integer.compare(a.getValue(), b.getValue()));
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            minHeap.add(entry);
            if (minHeap.size() > k) minHeap.poll(); 
        }

        List<Integer> res = new ArrayList<>();
        while(res.size()<k){
            Map.Entry<Integer, Integer> entry = minHeap.poll();
            res.add(entry.getKey());
        }
        return res;
}



// use treeMap. Use freqncy as the key so we can get all freqencies in order
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }
        
        TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
        for(int num : map.keySet()){
           int freq = map.get(num);
           if(!freqMap.containsKey(freq)){
               freqMap.put(freq, new LinkedList<>());
           }
           freqMap.get(freq).add(num);
        }
        
        List<Integer> res = new ArrayList<>();
        while(res.size()<k){
            Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
            res.addAll(entry.getValue());
        }
        return res;
    }
}

 

그나마 알아볼 수 있는 풀이

https://leetcode.com/problems/top-k-frequent-elements/discuss/754474/Easy-JAVA-Solution

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap();
        for(int n : nums){
            map.put(n,map.getOrDefault(n,0) + 1);//storing num and its freq
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->map.get(b) - map.get(a));
        //custom sort priority queue based on map values while adding the records to pq
        pq.addAll(map.keySet());
        int[] res = new int[k];
        for(int i = 0;i<k;i++){
            res[i] = pq.remove();
        }
        return res;
    }
}

// hashmap 생성
// foreach -> getOrDefault
// Map - getOrDefault(key, Default-value)
// getOrDefault는 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환한다.
// PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->map.get(b) - map.get(a));
// -> 우선순위를 부여하여 Integer형 queue를 생성 (그냥 queue는 FIFO)
//  PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); 같은 순서부여
// (a,b)->map.get(b) - map.get(a)는 무슨의미인가
// 람다식을 아직 잘 모르겠다

그나마 알아볼 수 있는 풀이2

https://leetcode.com/problems/top-k-frequent-elements/discuss/512339/Simple-JAVA-Brute-Force-Method-w-Comments-Clean-Code

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // Handle null data and edge cases
        if (nums == null || nums.length == 0) return new ArrayList<>();
        
        // Using a map to keep track of count
        Map<Integer, Integer> map = new HashMap<>();
        // Using a list to only keep unique nums and to then sort them
        List<Integer> list = new ArrayList<>();
        
        for (int num : nums) {
            // Add count to map
            map.put(num, map.getOrDefault(num, 0) + 1);
            // Add only unique nums to list
            if (!list.contains(num)) list.add(num);
        }
        
        // Sort list by greatest count to least
        Collections.sort(list, (Integer a, Integer b) -> map.get(b) - map.get(a));
        
        // Return a list containing only up to K elements
        return list.subList(0, k);
    }
}

Time Complexity: O(n log n)
Space Complexity: O(n)

---

링크

 

leetcode.com/problems/top-k-frequent-elements/

Top K Frequent Elements - LeetCode