题解 | #字符串出现次数的TopK问题#

题目主要信息:

题目要求为找到给定字符串数组中出现次数前k的字符串，按照出现频率由高到低排序输出，相同频率按照字典序
字符串的字符仅包含数字字母

具体思路:

很明显，这道题有两个要解决的问题，一个是统计各个字符串的出现频次，一个是找到出现次数前k的字符串然后输出。

对于第一个问题，统计频次可以使用unordered_map来实现，key值记录各个不同的字符串，value值记录其出现的次数，这是哈希表的一个操作。

对于第二个问题，可以考虑对统计好的频次排序，但是这样复杂度会比较高，因此我们只需要前k个，而不需要完整的排序，因此可以使用一个大小为k的优先队列，队列中记录的就是频次为k的字符串，频次太小的弹出队列即可。

step 1：用unordered_map构建一个哈希表，用于统计各个不同字符串出现的频次，遍历字符串数组统计每个字符串出现的频次。
step 2：用priority_queue构建一个优先队列（小顶堆），其中记录字符串及出现次数，并重载比较方式为先看频次再看字典序。
step 3：遍历哈希表，将字符串及频次加入优先队列中，限制队列长度为k，如果优先队列满了，则优先比较待加入元素与堆顶元素的频次，如果待加入的更大，则弹出堆顶后再加入，保证优先队列（小顶堆）中最多只有k个元素。
step 4：最后因为是小顶堆，弹出元素后需要逆序输出。

输入["b","a","c","b"],k=2的动图演示如下所示： alt

代码实现:

class Solution {
public:
    struct cmp {  //重载比较规则
    bool operator() (pair<string, int> p1, pair<string, int> p2) {
        //返回出现频率更高的或者相同时字典序更小的
        return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first); 
    }
    };
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        vector<vector<string> > res;
        unordered_map<string, int> mp; //统计字符串出现次数
        priority_queue<pair<string, int>, vector<pair<string, int> >, cmp> pq; //重载比较的小顶堆
        for(int i = 0; i < strings.size(); i++)  //次数加入哈希表
            mp[strings[i]]++;
        for(auto iter = mp.begin(); iter != mp.end(); iter++) { 
            if(pq.size() < k) //用k限制堆大小
                pq.push(pair<string, int> {iter->first, iter->second}); 
            //当超过k，需要判断是否将最小的取出加入新的
            else if(iter->second > pq.top().second || (iter->second == pq.top().second && iter->first < pq.top().first)) { 
                pq.pop();
                pq.push(pair<string, int> {iter->first, iter->second});
            }
        }
        while(!pq.empty()) { 
            res.push_back(vector<string> {pq.top().first, to_string(pq.top().second)});
            pq.pop();
        }
        reverse(res.begin(), res.end()); //逆转使优先级从大到小
        return res; 
    }
};

复杂度分析：

时间复杂度： $O (n l o g_{2} k)$ ，遍历数组统计字符串频次需要 $O (n)$ ，遍历哈希表找到出现最多的k个，最坏需要遍历 $n$ 次，每次加入优先队列的复杂度为 $O (l o g_{2} k)$
空间复杂度： $O (n + k)$ ，最坏情况下数组n个元素都是不同的，哈希表大小为 $n$ ，然后还需要长度为 $k$ 的优先队列