NC97 字符串出现次数的TopK问题

描述

给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。 返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。 对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。 比如"ah1x"小于"ahb"，"231"<”32“ 字符仅包含数字和字母

本题其实是 寻找第K大 这道题的变种，无非就是把整数的第K大变成了数据结构的第K大。

1. 排序

用一个哈希表维护每个字符串的出现频率，然后用pair<string, int>承载这个二元组，装到一个数组里，对这个结构自定义比较器，再取排序后数组的前k名即可。

class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    using psi = pair<string, int>;
    
    
    static bool cmp(const psi a, const psi b) {
        // 根据题意对排名的要求，维护大小关系
        return a.second == b.second ? a.first < b.first : a.second > b.second;
    }
    
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        unordered_map<string, int> m;
        vector<vector<string> > res;
        
        for(auto s : strings) m[s]++;
        
        vector<psi> temp;
        
        for (auto [k, v] : m) {
            temp.push_back({k, v});
        }
        
        sort(temp.begin(), temp.end(), cmp);
        
        // 取temp的前k名就行了
        for (int i = 0; i < k; i++)
            res.push_back({temp[i].first, to_string(temp[i].second)});
        return res;
    }
};

• 时间复杂度: $O(nlogn)O(nlogn)$, 一轮排序。
• 空间复杂度: $O(n)O(n)$, 定义了长度为n的数组temp。

2. 小根堆维护topk

先复习一下堆的概念:

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

父节点元素大于等于子节点的, 叫大根堆, 否则叫小根堆.

一个堆的示例如图所示：

计算机中， 我们使用数组模拟的完全二叉树来模拟堆， 上图的大根堆可以存储如下：

这道题建一个大小为k的小根堆, 遍历pair数组, 如果堆不满, 则入堆, 否则做如下判断:

• 如果堆顶元素小于等于当前元素, 说明这个数一定不会是第k大的, 原因很简单, 堆里面已经有k个数, 且都大于等于堆顶的那个, 因此丢弃;
• 如果堆顶元素大于当前元素, 去掉堆顶元素, 再把当前元素入堆

最后我们把整个堆存到一个数组中,注意是小根堆，所以每次push_back放进去的是最小的，因此要再反转一遍。

class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    using psi = pair<string, int>;
    
    static struct comparator {
        bool operator() (const psi a, const psi b) {
            return cmp(a, b);
        }
    };
    
    static bool cmp(const psi a, const psi b) {
        // 根据题意对排名的要求，维护大小关系
        return a.second == b.second ? a.first < b.first : a.second > b.second;
    }
    
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        unordered_map<string, int> m;
        vector<vector<string> > res;
        
        for(auto s : strings) m[s]++;
        
        vector<psi> temp;
        
        for (auto [k, v] : m) {
            temp.push_back({k, v});
        }
        
        priority_queue<psi, vector<psi>, comparator> pq;
        
        for (auto p : temp) {
            if (pq.size() < k) pq.push(p);
            else if (cmp(p, pq.top())) {
                pq.pop();
                pq.push(p);
            }
        }
        
        while(!pq.empty()) {
            psi temp = pq.top();
            pq.pop();
            res.push_back({temp.first, to_string(temp.second)});
        }
        
        reverse(res.begin(), res.end()); // 这里是小根堆，所以res和答案正好相反，再反过来就好了
        return res;
    }
};

• 时间复杂度: $O(nlogk)O(nlogk)$, 遍历了长度为n的pair数组，并且维护了k大小的堆，每次插入、调整都是对数复杂度。
• 空间复杂度: $O(k)O(k)$, 定义了长度为k的优先队列。