出现次数的TopK问题

#include <bits/stdc++.h>
using namespace std;

struct P{
    string s;
    int cnt;
    P(string s, int cnt):s(s),cnt(cnt){}
    bool operator<(P p)const{
        if(cnt == p.cnt)
            return s > p.s;
        return cnt < p.cnt;
    }
};

int main(){
    string s;
    int n, k;
    cin>>n>>k;
    unordered_map<string, int> mp;
    for(int i=0;i<n;i++){
        cin>>s;
        mp[s]++;
    }
    priority_queue<P> q;
    for(auto &p: mp)
        q.push(P{p.first, p.second});
    while(k--){
        cout<<q.top().s<<" "<<q.top().cnt<<endl;
        q.pop();
    }
    return 0;
}

#include<iostream>
(720)#include<cstdio>
#include<queue>
(789)#include<map>
using namespace std;
struct node{
    string s;
    int count;
    node(string ss,int ccount):s(ss),count(ccount){}
    bool operator<(const node &t)const{
        if(count!=t.count)
        {
            return count<t.count;
        }else{
            return s>t.s;
        }   
    }
};
int main(){
    int N,k;
    string s;
    map<string,int> m;
    scanf("%d %d",&N,&k);
    for(int i=0;i<N;++i){
       cin>>s;
       m[s]++;
    }
    priority_queue<node> q;
    map<string,int>::iterator it;
    for(it=m.begin();it!=m.end();++it){
        q.push(node(it->first,it->second));
    }
    while(!q.empty()&&k!=0){
        cout<<q.top().s<<" "<<q.top().count<<endl;
        q.pop();
        k--;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node{
    string str;
    int times;
    Node(string s, int t){
        str = s;
        times = t;
    }
    bool operator<(const Node& t)const{
        if(times != t.times){
            return times < t.times;
        }else{
            return str > t.str;
        }
    }
};
int main(){
    int n, k; cin >> n >> k;
    unordered_map<string, int> rmap;
    string s;
    for(int i=0; i<n; i++){
        cin >> s;
        if(rmap.count(s) != 0) rmap[s]++;
        else rmap[s] = 1;
    }
    priority_queue<Node> maxHeap;
    for(auto node : rmap){
        maxHeap.push(Node(node.first, node.second));
    }
    for(int i=0; i<k; i++){
        Node head = maxHeap.top(); maxHeap.pop();
        cout << head.str << " " << head.times << endl;
    }
    return 0;
}

hashmap+小顶堆

from collections import defaultdict
import heapq
class node:
    def __init__(self,val,index):
        self.val = val
        self.index = index
    def __lt__(self, other):
        if self.val == other.val:
            return self.index > other.index
        else:
            return self.val < other.val

n, k = map(int, input().split())
l = []
for i in range(n):
    l.append(input())
d = defaultdict(int)
for e in l:
    d[e] += 1

pq = []
for kk,v in d.items():
    heapq.heappush(pq, node(v,kk))
    if len(pq) > k:
        heapq.heappop(pq)
res = []
while len(pq) > 0:
    t = heapq.heappop(pq)
    res.insert(0,[t.val,t.index])
for e in res:
    print(e[1],e[0])