//
// Created by 罗炳国 on 2023/11/24.
//

#ifndef PFJ_CODE033_TOPKFREQUENT_H
#define PFJ_CODE033_TOPKFREQUENT_H

#include "commonHeader.h"

/**
 * 692. 前K个高频单词
 * 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
 * https://leetcode.cn/problems/top-k-frequent-words/
 * */

struct mapItem {
    string &str;
    int times;
};

bool dataItemCmp(struct mapItem *a, struct mapItem *b) {
    if (a->times > b->times)
        return true;
    if (a->times == b->times)
        return a->str.compare(b->str) < 0;
    return false;
}

struct itemcomp {
    bool operator()(struct mapItem *a, struct mapItem *b) {
        return dataItemCmp(a, b);
    }
};

class code033_topKFrequent {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> ans;
        unordered_map<string, struct mapItem *> um;
        priority_queue<struct mapItem *, vector<struct mapItem*>, itemcomp> pq;
        for (auto &str : words) {
            // 更新哈希表
            struct mapItem *item;
            auto iter = um.find(str);
            if (iter == um.end()) {
                item = new mapItem{str, 0};
                um[str] = item;
            }
            else
                item = iter->second;
            item->times++;
        }

        for (auto &item : um) {
            // 更新队列
            if (pq.size() < k) {
                pq.push(item.second);
                continue ;
            }
            if (dataItemCmp(item.second, pq.top())) {
                pq.pop();
                pq.push(item.second);
            }
        }

        while (!pq.empty()) {
            ans.push_back(pq.top()->str);
            pq.pop();
        }
        std::reverse(ans.begin(), ans.end());
        return ans;
    }

    void test() {
        vector<string> vecs{"the","day","is","sunny","the","the","the","sunny","is","is"};
        vector<string> ans = topKFrequent(vecs, 4);
        vecShow(ans);
    }

};

#endif//PFJ_CODE033_TOPKFREQUENT_H