LeetCode 692题解 | 前K个高频单词

一、题目链接

692.前K个高频单词

二、题目

三、分析

本题目我们利用map统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。

解法一：用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的。

涉及到排序的稳定性，稳定性好的排序是：冒泡、插入、归并，保证相等的值的相对顺序不变。

算法库里有一个稳定的排序（底层是归并，用其他的稳定的排序效率太低）：

解法二：不用stable_sort有什么办法解决呢？将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。

四、代码

解法一：

class Solution {
public:
    // stable_sort与库里的pair比较行为不符，自定义比较器——定制仿函数
    struct Compare
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            return kv1.second > kv2.second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 次数
        map<string, int> countMap;
        for (auto& e : words)
        {
            countMap[e]++;
        }
        // 排降序 —— map的数据倒过来，字典序排过了
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        // 仿函数控制降序
        stable_sort(v.begin(), v.end(), Compare());
        /* LeetCode平台支持打印 */
        //for (auto& e : v)
        //{
        //    cout << e.first << ":" << e.second << endl;
        //}

        vector<string> ret;
        for (int i = 0; i < k; ++i)
        {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

解法二：

class Solution {
public:
    // stable_sort与库里的pair比较行为不符，自定义比较器——定制仿函数
    struct Compare
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 次数
        map<string, int> countMap;
        for (auto& e : words)
        {
            countMap[e]++;
        }
        // 排降序
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        // 仿函数控制降序，仿函数控制次数相等，字典序小的在前面
        sort(v.begin(), v.end(), Compare());
        // 取前k个
        vector<string> ret;
        for (int i = 0; i < k; ++i)
        {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

class Solution {
public:
    // stable_sort与库里的pair比较行为不符，自定义比较器——定制仿函数
    struct Compare
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            // 要注意优先级队列底层是反的，大堆要实现小于比较，所以这里次数相等，想要字典序小的在前面要比较字典序大的为真
            return kv1.second < kv2.second || (kv1.second == kv2.second && kv1.first > kv2.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 次数
        map<string, int> countMap;
        for (auto& e : words)
        {
            countMap[e]++;
        }
        // 将map中的<单词，次数>放到priority_queue中，仿函数控制大堆，次数相同按照字典序规则排序
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(countMap.begin(), countMap.end());

        vector<string> ret;
        for (int i = 0; i < k; i++)
        {
            ret.push_back(p.top().first);
            p.pop();
        }
        return ret;
    }
};