347. Top K Frequent Elements

1. use maxHeap,

O(nlogn), O(n)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. use hashmap to store freq
        // 2. use maxheap or bucket sort to find top k freq elements
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        
        maxHeap.addAll(map.keySet());
        
        List<Integer> result = new ArrayList<>();
        for (int i = maxHeap.size() - 1; i >=0 && result.size() < k; i--) {
            result.add(maxHeap.remove());
        }
        
        return result.stream().mapToInt(i->i).toArray();
        
    }
}

2. use minHeap

T: O(nlogk)

S: O(n)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) { 
            freq.put(num, freq.getOrDefault(num, 0)+1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((a, b) ->{
            return a.getValue() - b.getValue();
        });
        
        for (Map.Entry<Integer, Integer> m : freq.entrySet()) {
            queue.offer(m);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        
        int[] res = new int[queue.size()];
        int i = 0;
        while (!queue.isEmpty()) {
            res[i++] = queue.poll().getKey();
        }
        return res;
    }
}
/*
num, freq

minheap
*/

2. use bucket sort

O(n), O(n)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. use hashmap to store freq
        // 2. use maxheap or bucket sort to find top k freq elements
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        
        List<Integer> bucket[] = new List[nums.length + 1]; // notice this!
        for (Integer key : map.keySet()) {
            int freq = map.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = bucket.length - 1; i >= 0 && result.size() < k; i--) {
            if (bucket[i] != null) {
                result.addAll(bucket[i]); // notice this!
            }
        }
        return result.stream().mapToInt(i->i).toArray();
    }
}