not able to undersatnd solution
read tutorial also…then also didn’t got
Top k most freq no in a stream...challenges heap
hello @hg11110000
mantain k size window that store top k frequent number.
now let say a new number comes , updated its frequency and then check it can be a part of our window or not.
how ? find the element which has least frequncy . if this frequency is less than our current element frequncy then we discard that least frequent element and add thr current element in our window.
this was the idea. now to make the second step more efficient we will always keep our window sorted (by frequncy) and use insertion sort logic for finding best position of our newly inserted element.
now read the editorial again , it will make more sense
@aman212yadav
#include<bits/stdc++.h>
using namespace std;
#define int long long int
class abc
{
public:
bool operator()(pair<int, int> p1, pair<int, int> p2)
{
return p1.second > p2.second;
}
};
int32_t main()
{
int t; cin >> t;
while (t--)
{
int n, k; cin >> n >> k;
int a[n];
map<int, int, abc> m;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i)
{
m[a[i]]++;
}
for (auto p : m) cout << p.first << "->" << p.second << endl;
}
return 0;
}
this shows error…how can i put a custom comparator for a map ??
@hg11110000
pls share ur code using cb ide .
by defining functors and passing it as third argument of map
i did that only…but shwoing errors…
chekc ur shared code again,it does not contain any functor
can u edit it please and show how to implement ?
ur map key is of type int but here u r passing pair thats why it is not working.
note : we can write comprator only for keys of map and not on their value
it not possible to sort mapn by its value using comparator.
here are some other techniques for sorting based on value that u can refer ->link