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

1. 用map统计次数
2. 用结构体表示(str, count) 放入到vector中进行排序
3. 排完序取前k个作为结果

public:
    map<string, int>count;
    
    struct node{
        string str;
        int c;
        node(string str, int c): str(str), c(c){}
    };
    
    static bool cmp(node a, node b){
        if(a.c == b.c)
            return a.str < b.str;  // 频数一样时，字典序小的排前面
        else return a.c > b.c;  // 频数大的在前面
    }
    
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        vector<vector<string>>res;
        
        for(int i=0; i<strings.size(); i++)  // 统计次数
            count[strings[i]]++;
        
        // 把map里的放到vec中准备排序
        map<string, int>::iterator it;
        vector<node>vec;
        for(it=count.begin(); it!=count.end(); it++){
            vec.push_back(node(it->first, it->second));
        }
        sort(vec.begin(), vec.end(), cmp);

        // 排完序后取前k个放到结果里
        for(int i=0; i<k; i++)
            res.push_back({vec[i].str, to_string(vec[i].c)});
        
        return res;
    }
};