347 Top K Frequent Elements ***** imp & hard

Given a non-empty array of integers, return the k most frequent elements.

For example, Given[1,1,1,2,2,3]and k = 2, return[1,2].

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

priorityqueue, bucket sort, treeset

PriorityQueue : time : O(nlogn) space : O(n)

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((a,b) -> b.getValue() - a.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.offer(entry);
        }
        for (int i = 0; i < k; i++) {
            ans.add(queue.poll().getKey());
        }
        return ans;
    }
}

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        if(nums == null || nums.length == 0) {
            return ans;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        TreeMap<Integer, List<Integer>> set = new TreeMap<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int freq = entry.getValue();
            if (!set.containsKey(freq)) {
                set.put(freq, new ArrayList<>());
            }
            set.get(freq).add(entry.getKey());
        }
         while (ans.size() < k) {  // O(klogn)
            Map.Entry<Integer, List<Integer>> entry = set.pollLastEntry();
            ans.addAll(entry.getValue());
        }
        return ans;
    }
}

Bucket:

List<Integer>[] bucket = new List[nums.length + 1];

not new List<Integer>[nums.length + 1];

this is a frequency bucket, so if all the element is 1 in the array for example [1,1,1,1] then you initialize a five length array so that it will include a frequency of 4

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        List<Integer>[] bucket = new List[nums.length + 1];
        //[1111]
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int key : map.keySet()) {
            int freq = map.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }
        for (int i = bucket.length - 1; i >= 0 && ans.size() < k; i--) {
            if(bucket[i] != null) {
                ans.addAll(bucket[i]);
            }
        }
        return ans;
    }
}