Statement - Given an array A[] of integers, sort the array according to frequency of elements. That is elements that have higher frequency come first. If frequencies of two elements are same, then smaller number comes first.
Test Case -
1
37
1 3 7 7 7 3 2 2 2 7 3 1 7 1 6 3 5 5 4 5 6 2 1 2 4 7 3 1 3 5 4 1 7 2 6 1 2
output is:
1 1 1 1 1 1 1 2 2 2 2 2 2 2 7 7 7 7 7 7 7 3 3 3 3 3 3 5 5 5 5 4 4 4 6 6 6
Code - Using hash map and heap time complexity O(nlogn).
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define lc "\n"
#define inf 1e18+1
#define f ios_base::sync_with_stdio(false)
#define ss cin.tie(NULL)
#define ts to_string
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for(int i = a; i <= b; i++)
struct cmp {
constexpr bool operator()(
pair<int, int> const& a,
pair<int, int> const& b)
const noexcept
{
if(a.first == b.first)
return a.second > b.second;
return a.first < b.first;
}
};
void test_case()
{
int n;
cin >> n;
vector<int> v(n);
for(auto &a : v) cin >> a;
unordered_map<int, int> um;
for(auto a : v)
um[a]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
for(auto a : um)
{
pq.push(make_pair(a.second, a.first));
}
while(!pq.empty())
{
auto a = pq.top();
pq.pop();
for(int i = 0; i < a.first; i++)
{
cout << a.second << " ";
}
}
}
int main()
{ f;ss;
int t;
cin >> t;
while(t--)
{
test_case();
cout << lc;
}
return 0;
}
Offers
0 Comments