Top K Frequent Elements

LeetCode Q 347 - Top K Frequent Elements

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

Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 ; Output: [1,2]
Example 2:
Input: nums = [1], k = 1 ; Output: [1]
Note: 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.

Solution

Heap Sort: time O(NlogN)
Bucket Sort: tiem O(N)

Solution 1: Heap Sort

Code:

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

	Queue<Integer> pq = new PriorityQueue<>((a, b) -> (map.get(a) - map.get(b)));
	
	for (int num: map.keySet()) {
		pq.offer(num);
		if (pq.size() > k) pq.poll();
	}

	List<Integer> res = new ArrayList<>();
	for (int num: pq)
		res.add(0, num);

	return res;
}

Solution 2: Bucket Sort (Counting sort)

Code:

public List<Integer> topKFrequent(int[] nums, int k) {
	Map<Integer, Integer> map = new HashMap<>();
	List<Integer>[] lists = new int[nums.length + 1];
	
	// first traverse: calculate frequencies, recode in the map
	Map<Integer, Integer> map = new HashMap<>();
	for (int num: nums) 
		map.put(num, map.getOrDefault(num, 0) + 1);

	// build buckets
	for (int num: map.keySet()) {
		int freq = map.get(num);
		if (lists[freq] == null) lists[freq] = new ArrayList<>();
		lists[freq].add(num);
	}

	// traverse each bucket 
	List<Integer> res = new ArrayList<>();
	for (int i = lists.length - 1; i >= 0 && k != 0; i--) {
		if (lists[i] == null) continue;
		res.addAll(lists[i]);
		k -= lists[i].size();
	}

	return res;
}