牛客網-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;
    }
};