谈一谈你所理解的TopK问题

       在实际的应用和工作当中, 我们经常会遇到在海量的数据当中寻找出前K个最大值或最小值的问题, 为了实现这个功能, 我们最先想到的方法可能就是排序, 在排序之后的序列当中取出前K个即可, 这样的方法确实可以, 但是存在一定的问题, 千万不要忘了这个问题的前提海量数据, 这就也就是说当数据规模过大内存放不下的时候, 我们再去使用常见的排序就无法解决.

因此, 对于这种海量数据的TopK问题, 一种经常使用的方法就是借助堆去解决

使用堆去解决TopK问题的原理

首先我们需要考虑清楚, 我们需要建立一个大堆还是小堆.
如果我们需要的是前K个最大值, 那么建立可以存储K个值的小堆
如果我们需要的是前K个最大值, 那么建立可以存储K个值的大堆

我们那一种情况去距离说明, 假如我们需要取到海量数据前K个最大的值, 首先我们建立K个数据的小堆, 因为我们建立的是小堆, 这也就是说此时堆顶的数据是最小的! 因此, 接下来的操作就是, 将剩下的数据依次拿出来与堆顶数据做比较, 假如当前数据大于堆顶数据, 就删除堆顶数据, 插入当前数据, 最终堆中所存储的K个值就是我们想要的.

在C++的STL库中提供了优先级队列 priority_queue ,默认为大堆, 可以通过传入仿函数的方式改变优先级队列的优先级.

应用场景

关于时间复杂度: 假设数据量为n, 要找到TopK元素, 堆每次插入和删除的时间复杂度为O(logK). 在最坏的情况下, 对于每一个元素都需要进行堆的插入和删除, 也就是说最坏的时间复杂度为O(nlogK), 最好的情况是, 前K个元素即为我们要寻找的TopK, 这个时候堆不需要调整, 此时时间复杂度为O(n).

使用场景

关于TopK的使用场景非常多, 比如统计前K个高频元素, 海量字符串查询记录, 某天访问网站次数最多的前K个IP等等, 这些都属于TopK问题, 这里给出一个TopK问题的题目, 可以做一做, 加深影响.

前 K 个高频元素

代码示例:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ret;
        
        unordered_map<int, int> m;
        for (int i = 0; i < (int)nums.size(); ++i)
        {
            m[nums[i]]++;//统计次数
        }

        //小堆
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        //priority_queue<pair<int, int>> q;

		//可以使用 auto简化
		//for (auto it = m.begin(); it != m.end(); ++it)
        for (unordered_map<int, int>::iterator it = m.begin(); it != m.end(); ++it)
        {
            if (q.size() == k)
            {
                if (it->second > q.top().first)
                {
                    q.pop();
                    q.push(make_pair(it->second, it->first));
                }
            }
            else
            {
                q.push(make_pair(it->second, it->first));//按出现的次数排序
            }
        }

        while (!q.empty())
        {
            ret.push_back(q.top().second);
            q.pop();
        }
		
        //reverse(ret.begin(), ret.end()); 根据题目要求再确定是否需要翻转

        return ret;
    }
};