Hello Everyone,
Print the elements of an array in the decreasing frequency if 2 numbers have the same frequency then print the one which came first.
Examples:
Input : arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output : arr[] = {8, 8, 8, 2, 2, 5, 5, 6}
Input : arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output : arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
All of the above approaches work in O(n Log n) time where n is total number of elements. In this post, a new approach is discussed that works in O(n + m Log m) time where n is total number of elements and m is total number of distinct elements. The idea is to use hashing.
- We insert all elements and their counts into a hash. This step takes O(n) time where n is number of elements.
- We copy the contents of hash to an array (or vector) and sort them by counts. This step takes O(m Log m) time where m is total number of distinct elements.
- For maintaining the order of elements if the frequency is the same, we use another hash which has the key as elements of the array and value as the index. If the frequency is the same for two elements then sort elements according to the index.
We do not need to declare another map m2, as it does not provide the proper expected result for the problem. instead, we need to just check for the first values of the pairs sent as parameters in the sortByVal function.
Below is the implementation of the above approach:
// CPP program for the above approach
#include <bits/stdc++.h>
using
namespace
std;
// Used for sorting by frequency. And if frequency is same,
// then by appearance
bool
sortByVal(
const
pair<
int
,
int
>& a,
const
pair<
int
,
int
>& b)
{
// If frequency is same then sort by index
if
(a.second == b.second)
return
a.first < b.first;
return
a.second > b.second;
}
// function to sort elements by frequency
vector<
int
>sortByFreq(
int
a[],
int
n)
{
vector<
int
>res;
unordered_map<
int
,
int
> m;
vector<pair<
int
,
int
> > v;
for
(
int
i = 0; i < n; ++i) {
// Map m is used to keep track of count
// of elements in array
m[a[i]]++;
}
// Copy map to vector
copy(m.begin(), m.end(), back_inserter(v));
// Sort the element of array by frequency
sort(v.begin(), v.end(), sortByVal);
for
(
int
i = 0; i < v.size(); ++i)
while
(v[i].second--)
{
res.push_back(v[i].first);
}
return
res;
}
// Driver program
int
main()
{
int
a[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };
int
n =
sizeof
(a) /
sizeof
(a[0]);
vector<
int
>res;
res = sortByFreq(a, n);
for
(
int
i = 0;i < res.size(); i++)
cout<<res[i]<<
" "
;
return
0;
}
Output:
8 8 8 2 2 5 5 6 -1 9999999
Time Complexity : O(n) + O(m Log m) where n is total number of elements and m is total number of distinct elements