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

字符串出现次数的TopK问题
题意:
给定一个字符串数组，再给定整数k，返回出现次数前k名的字符串和对应的次数。

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

案例
输入：["123","123","231","32"],2
返回值：[["123","2"],["231","1"]]
说明："123"出现了2次，记["123","2"]，"231"与"32"各出现1次，但是"231"字典序在"32"前面，记["231","1"]，最后返回[["123","2"],["231","1"]]

方法一 map+小根堆

首先统计所有字符串出现个数使用unordered_map来存储，之后使用小根堆的方式对每次插入的答案进行长度为k的维护，最后将答案存入vector返回即可

struct cmp{ //小根堆排序条件
    bool operator()(pair<int, string> &a, pair<int, string> &b){
        return a.first > b.first || (a.first == b.first && a.second < b.second); //数字大的在前面如果数字相同则按字符串字典序排序
    }
};
class Solution {
public:

    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        unordered_map<string, int> mp;
        for(int i = 0; i < strings.size(); i ++){ //记录字符串出现次数
            mp[strings[i]] ++;
        }
        priority_queue<pair<int, string>, vector<pair<int,string>>, cmp> d;
        vector<vector<string> > ans(k);
        for(auto [a, b]: mp){ 
            if(d.size() < k) d.push({b, a}); //如果堆中小于k个元素则直接添加
            else{
                if(d.top().first < b || (d.top().first == b && d.top().second > a)){//如果大于k个元素则对堆顶最小的元素和当前元素最对比如果当前元素大于堆顶则替换堆顶元素
                    d.pop(); d.push({b, a});
                }
            }
        }
        while(d.size()){    //将答案存入vector中
            vector<string> res;
            res.push_back(d.top().second); res.push_back(to_string(d.top().first));
            ans[-- k] = res;
            d.pop();
        }
        return ans;
    } 
};

时间复杂度: 统计数量最大复杂度为,小根堆维护最大的长度为k个所以总体复杂度为
空间复杂度: 统计时最多会用到的空间

方法二 排序

统计所有字符串出现的次数后对整体进行排序,取前k大的元素返回即可。

int cmp(pair<string, int> a, pair<string, int> b){ //排序条件
        if(a.second == b.second) return a.first < b.first;
        return a.second > b.second;
    };
class Solution {
public:

    pair<string, int> arr[100010];

    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        unordered_map<string, int> mp;
        for(int i = 0; i < strings.size(); i ++){ //统计字符串出现个数
            mp[strings[i]] ++;
        }
        int tot = 0;
        for(auto [a, b] : mp){//将统计内容放入数组中
            arr[++ tot] = make_pair(a, b);
        }
        sort(arr + 1, arr + tot + 1, cmp); //排序
        vector<vector<string> > ans;
        for(int i = 1; i <= k; i ++){ //取前k大的元素
            vector<string> res;
            res.push_back(arr[i].first); res.push_back(to_string(arr[i].second));
            ans.push_back(res);
        }
        return ans;
    }
};

时间复杂度: 排序需要的复杂度
空间复杂度: 统计和存储时最多会用到的空间