881427. K Most occurring elements
Here is a detailed Markdown blog post for the problem:
K Most Occurring Elements
Slug: most-occurring-elements-1587115620--143034 Difficulty: Medium Id: 881427 Topic Tags: Heap, Data Structures Company Tags: None
Summary
Given an array of integers, we need to find the k most occurring elements in the array. This problem involves using a heap data structure and sorting algorithms.
Detailed Explanation
To solve this problem, we can use a priority queue or a max heap to keep track of the frequency of each element in the array. We iterate through the array, counting the frequency of each element. When the size of the priority queue exceeds k, we remove the smallest frequency element from the queue until its size is less than or equal to k.
Here's a step-by-step breakdown of the solution:
- Create an empty max heap (priority queue) and insert the first element of the array into it along with its frequency.
- Iterate through the rest of the array:
- For each element, increment its frequency in the priority queue if it already exists. If not, insert it into the queue along with its frequency.
- If the size of the priority queue exceeds k, remove the smallest frequency element from the queue until its size is less than or equal to k.
- The elements in the priority queue are now the k most occurring elements in the array.
Time complexity analysis:
- Iterating through the array takes O(n) time where n is the length of the array.
- Inserting and removing elements from the priority queue takes O(log k) time, as we're using a max heap with k elements.
- Total time complexity: O(n log k)
Space complexity analysis:
- We need to store the frequency of each element in the priority queue, which takes O(k) space.
Optimized Solutions
Java
import java.util.PriorityQueue;
public class KMostOccurringElements {
public static int[] findKMostOccurring(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
pq.offer(entry.getKey());
if (pq.size() > k) {
pq.poll();
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pq.poll();
}
return result;
}
}