Daily C/C++ stl小应用

stl小应用

前几天有看到一些stl函数，恰好今天的leetcode的每日一题可以让我们把这些函数运用上来

要用到的函数主要有

sort()
transform()
nth_element()
accumulate()

先看题

题意很简单，就是叫我们统计出词频前K大的单词

这里先说我解决这道题的思路，复杂度应该是O(n + klogk)的，理论上是比官方的O(nlogk)要更好一些的

但是应该是我常数写的比较大导致最后结果比较慢

思路就是首先用哈希表统计出每个单词的词频，然后用nth_element来找出前k个，最后再在前k个中排序就行

那么这里我们给出我们的函数式的代码

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> ans;
        auto mp = accumulate(
            words.begin(), words.end(), 
            unordered_map<string, int>(), 
            [](unordered_map<string, int> mp, const string &word) {
                mp[word]++;
                return mp;
        });
        vector<pair<string, int>> tmp(mp.cbegin(), mp.cend());
        auto cmp = [](const pair<string, int> &lhs, const pair<string, int> &rhs) {
            if (lhs.second == rhs.second)
                return lhs.first < rhs.first;
            return lhs.second > rhs.second;
        };
        nth_element(tmp.begin(), tmp.begin() + k - 1, tmp.end(), cmp);
        sort(tmp.begin(), tmp.begin() + k, cmp);
        transform(tmp.begin(), tmp.begin() + k, back_inserter(ans), [](const pair<string, int> &x) {
            return x.first;
        });
        return ans;
    }
};

注意，前面统计词频的这块，我是为了用accumulate才用的，而不是说解决这个问题要用这种方法

因为这里我们是传的哈希表，还不是引用的形式，所以导致我换了这种写法比正常慢了9倍

所以正常写应该创建个哈希表，然后遍历一遍words就可以

accumulate的讲解可以看我的另一篇文章，这里我们就是简单的传入了一个空的哈希表作为初始值，然后对于每个word，在哈希表中把对应的词频+1既可

然后我们把哈希表转换成一个vector

用lambda表达式写出我们比较词频的比较函数，这里如果相同的词频，我们就按照字典序返回

调用nth_element，第一个参数和第三个参数用来限定排序的范围

第二个参数用来确定是取到第几个值，第四个参数用来传递比较函数

最终的结果就是他会在tmp.begin(), tmp.begin() + k - 1中储存前k大的单词，但是不保证这k个单词有序

然后我们再在这前k个中排序

最后就是输出结果了，因为我们的类型是pair，我们需要返回的是每个pair的first元素，所以用transform即可

最后提一嘴，我写这个代码还不多，风格和效率还不能完全兼顾，见谅