Problem: Given an array of size n and a value k, the task is to find k numbers with the highest frequencies. If there are multiple numbers with the same frequency, then the lesser number in the number line should be given priority.
Examples:
Input: arr[] = {3, 1, 4 , 4, 5, 2, 6, 1}
n = 8
k = 2
Output: 1 4
Explanation: Both 1 and 4 occur 2 times in the array, so we choose the smaller number 1 first.
Input: arr[] = {1, 1, 4, 4}
n = 4
k = 1
Output: 1
Explanation: Both 1 and 4 occur 2 times in the array, but we choose the smaller number 1 because of the priority given to it.
Approach: We can solve this problem efficiently using the concept of an unordered map, a vector, and a priority queue. The logic is to find the frequency of each element in the array and store it in an unordered map. Then, we create a vector of pairs from the unordered map, where the first element of the pair is the number, and the second element is its frequency. Next, we convert this vector into a priority queue, where the elements are arranged based on their frequency. We also define a compare function that prioritizes the smaller number when two pairs have the same frequency. Finally, we extract the k most frequent numbers from the priority queue.
Here are the steps of the approach:
Step 1: Create an unordered map to store the frequency of each element.
Step 2: Store the elements and their frequency in the unordered map.
Step 3: Create a vector of pairs from the unordered map, where the first element of the pair is the number, and the second element is its frequency.
Step 4: Convert the vector of pairs into a priority queue, where the elements are arranged based on their frequency.
Step 5: Define a compare function that prioritizes the smaller number when two pairs have the same frequency.
Step 6: Extract the k most frequent numbers from the priority queue.
Here's the code in Java:
import java.util.*;
public class Main {
// Compare method to arrange the priority_queue
// according to the frequency or lesser value
// in case the frequency of two pair matches.
static class Compare implements Comparator<Map.Entry<Integer, Integer>> {
public int compare(Map.Entry<Integer, Integer> p1, Map.Entry<Integer, Integer> p2) {
// If the frequency matches, return the lesser value.
if (p1.getValue().equals(p2.getValue())) {
return Integer.compare(p1.getKey(), p2.getKey());
}
// Otherwise, return the pair with the higher frequency.
return Integer.compare(p2.getValue(), p1.getValue());
}
}
// Method to find the k-most frequent numbers.
static void kMostFrequent(int[] arr, int n, int k) {
// Create an unordered map to store the frequency of each element.
Map<Integer, Integer> freq = new HashMap<>();
// Store the elements and their frequency in the unordered map.
for (int i = 0; i < n; i++) {
freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
}
// Create a list of map entries from the unordered map.
List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(freq.entrySet());
// Sort the list of map entries based on frequency and the lesser value if the frequency of two entries are the same
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
if (e1.getValue().equals(e2.getValue())) {
return e1.getKey().compareTo(e2.getKey());
} else {
return e2.getValue().compareTo(e1.getValue());
}
}
});
// Loop through the sorted list and add the k most frequent elements into a result list
List<Integer> result = new ArrayList<>();
for (int i = 0; i < k && i < list.size(); i++) {
result.add(list.get(i).getKey());
}
// Return the result list
return result;
The `findKMostFrequent` method first creates a `HashMap` to store the frequency of each element in the input array. It then creates a list of map entries from the `HashMap`. The list is sorted using a custom `Comparator` that first compares the frequency of the entries and then the value of the entries if their frequencies are the same. The sorted list is then looped through to add the k most frequent elements into a result list. Finally, the result list is returned.
This approach has a time complexity of O(n log n) due to the sorting operation. However, it has a space complexity of O(n) since it uses a `HashMap` to store the frequency of each element in the input array.
Overall, this approach provides a simple and easy-to-understand solution to the problem of finding the k most frequent elements in an array.
