Table of Contents
Problem Statement
In sort elements by frequency of occurrences problem, we have given an array a[]. Sort array elements in such a way that the element with the highest number of occurrences comes first. If the number of occurrences is equal then the print the number which appeared first in the array.
Input Format
First-line containing an integer value N.
Second-line containing N integer values.
Output Format
Print input array elements in a single line. such a way that the frequency of a[i] is greater than or equal to the frequency of a[i+1].
Constraints
- 1<=N<=100000
- -1e9<=arr[i]<=1e9
Explanation for Sort Elements by Frequency of Occurrences
The question involves two prime problems
- Sorting via frequency and
- Maintaining order for resolving clash.
We make use of two advanced and powerful data structures namely :
MAP and MULTIPMAP.
Map has the property of mapping some key to the value. Multimap does the same function but in addition to maps, it maintains the key in sorted fashion and specific order. Exactly the function we require.
Algorithm for Sort Elements by Frequency of Occurrences
1. Add the elements in the map ( map<int, int> ).
a. If they are not present then add them and make the count 1.
b. Else increment the count of the value by 1 as it occurred again. Map makes <value, frequency> pairs.
2. Now traverse the map and keep adding the elements into multimap in this way :
a. Make the 2nd field of map i.e the frequency of the map, as the key of multimap so that we get it automatically sorted.
b. Map the first value to the second so each entry in multimap holds <frequency, value> in ascending order on frequency.
3. Now simply traverse the multimap in reverse order to get the desired output.
Implementation
C++ Program for Sort Elements by Frequency of Occurrences
#include <bits/stdc++.h>
using namespace std;
typedef multimap<int, int> MapType;
int main()
{
int N;
cin>>N;
int a[N];
for(int i=0;i<N;i++)
{
cin>>a[i];
}
//Map uses the first id as the array element and second as the count of occurrences of the element
map<int,int> mp;
for(int i=0;i<N;i++)
{
//if the array element is present then just increase the count of occurence of it by 1
if(mp.find(a[i])!=mp.end()){
mp[a[i]]++;
}
else{
//if the array element is not present in the map already then add it
mp[a[i]]=1;
}
}
//it maintains specific order and count and while inserting makes it sorted
multimap<int,int> mp2;
map<int,int>::iterator it;
for(it=mp.begin();it!=mp.end();it++){
//Second becomes the key as we need to sort according to frequency.
mp2.insert(MapType::value_type(it->second,it->first));
}
map<int,int>::reverse_iterator itr;
for(itr=mp2.rbegin();itr!=mp2.rend();itr++)
{
//Reverse the multimap and print so that it prints in decreasing order.
for(int i=0;i<itr->first;i++)
cout<<itr->second<<"\t";
}
return 0;
}Java Program for Sort Elements by Frequency of Occurrences
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
class SortComparator implements Comparator<Integer> {
private final Map<Integer, Integer> freqMap;
// Assign the specified map
SortComparator(Map<Integer, Integer> tFreqMap)
{
this.freqMap = tFreqMap;
}
// Compare the values
@Override
public int compare(Integer k1, Integer k2)
{
// Compare value by frequency
int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));
// Compare value if frequency is equal
int valueCompare = k1.compareTo(k2);
// If frequency is equal, then just compare by value, otherwise -
// compare by the frequency.
if (freqCompare == 0)
return valueCompare;
else
return freqCompare;
}
}
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sr.nextInt();
}
Map<Integer, Integer> map = new HashMap<>();
List<Integer> outputArray = new ArrayList<>();
for (int current : arr)
{
int count = map.getOrDefault(current, 0);
map.put(current, count + 1);
outputArray.add(current);
}
// Compare the map by value
SortComparator comp = new SortComparator(map);
// Sort the map using Collections CLass
Collections.sort(outputArray, comp);
// Final Output
for (Integer i : outputArray)
{
System.out.print(i + " ");
}
}
}8 2 5 2 8 5 6 8 8
8 8 8 2 2 5 5 6
Complexity Analysis for Sort Elements by Frequency of Occurrences
Time Complexity
O(NlogN) where N is the number of elements present in the array. Here we arrange elements in sorted multimap.
Space Complexity
O(N) because here we use multimap and map which have maximum size up to N.