LintCode 550. 最常使用的K个单词II（自定义set（可修改数据的优先队列） + map）

1. 题目

在实时数据流中找到最常使用的k个单词. 实现TopK类中的三个方法:

• TopK(k), 构造方法
• add(word), 增加一个新单词
• topk(), 得到当前最常使用的k个单词.

代码语言：javascript复制

样例 1:
输入：
TopK(2)
add("lint")
add("code")
add("code")
topk()
输出：["code", "lint"]
解释：
"code" 出现两次并且 "lint" 出现一次， 它们是出现最频繁的两个单词。

样例 2:
输入：
TopK(1)
add("aa")
add("ab")
topk()
输出：["aa"]
解释：
"aa" 和 "ab" 出现 , 但是aa的字典序小于ab。

注意事项
如果两个单词有相同的使用频率, 按字典序排名.

2. 解题

• 优先队列，修改内部数据很麻烦，利用set，自定义其排序规则
• 遇到要更新的数据，先删除旧的数据，再插入更新的
• 遇到两点需要注意的，比较操作，必须const，查找存在，不能count，可能是因为自定义 set 的原因。

代码语言：javascript复制

unordered_map<string, int> wc;
struct cmp {
    bool operator()(const string &a,const string &b) 
    {   //必须写const，不写报错
        if (wc[a] == wc[b])
            return a < b;
        return wc[a] > wc[b];
    }
};

class TopK {
private:
    set<string,cmp> q;
    int K;
public:
    TopK(int k) { K = k;}

    void add(string word) {
        if (q.find(word) != q.end())//必须用find，不能用count
            q.erase(word);
        wc[word]  ;
        q.insert(word);
        if (q.size() > K)
            q.erase(--q.end());
    }

    vector<string> topk() {
        return vector<string> (q.begin(), q.end());
    }
};

100% 数据通过测试 总耗时 1314 ms 您的提交打败了 37.80% 的提交!

add count set word

0 人点赞