牛客网-NC97 字符串出现次数的TopK问题

一、题目

二、思路

1、利用map容器将数据添加到map容器中

2、将map容器中的数据添加到vector容器中

3、利用lambda函数使用partial_sort()函数对vector容器进行排序

函数对象：

auto cmp = [](const pair<string, int>& p1, const pair<string, int> p2) {
            if (p1.second != p2.second)
                return p1.second > p2.second;
            return p1.first < p2.first;
        };
           

4、将前k个添加到输出数组中

三、代码

class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        vector<string>res;
        vector<vector<string>>OutPut;
        if(strings.empty())
        {
            return OutPut;
        }
        
        //构建map容器
        map<string,int>Dic;
        int size=strings.size();
        for(int i=0;i<size;++i)
        {
            Dic[strings[i]]++;
        }
        
        //构建vector容器，把map容器的数据添加到vector容器
        //利用sort进行排序
        vector<pair<string,int>>ReverseDic;
        for(auto it=Dic.begin();it!=Dic.end();++it)
        {
            ReverseDic.emplace_back(make_pair(it->first,it->second));
        }
        
        //lambda函数排序
        auto comp=[](const pair<string,int>&a,const pair<string,int>&b){if(a.second!=b.second){return a.second>b.second;}return a.first<b.first;};
        //部分排序
        partial_sort(ReverseDic.begin(),ReverseDic.begin()+k,ReverseDic.end(),comp);
        for(int i=0;i<k;++i)
        {
            res.emplace_back(ReverseDic[i].first);
            res.emplace_back(to_string(ReverseDic[i].second));
            OutPut.emplace_back(res);
            res.clear();
        }
        return OutPut;
    }
};