本文总结下TopK相关算法，分为两个部分，一为讨论TopK问题的类型，二为相关的解题思路和C++代码实现。

TopK 问题一般为海量数据问题，可以分为两大类：

  • 找最大/最小的 K 个数

  这种问题一般分为两种类型，一为内存不够无法一次性加载，二为内存充足可以完全处理数据。

  • 找重复次数最大的 K 个数

  这种问题一般是涉及极其庞大的数据量，内存不可能一次性加载完成。必须采用 分治法。

TopK 问题

找最大最小的k个数

  • 利用大/小顶堆 + hashmap

例如找最大的K个数，利用一个大小为k的最小堆，每次数据和堆顶比较，若大于堆顶，则将堆顶移出，并把数据放入堆，排序，否则则忽略。HashMap在这里的作用是避免重复数据。

这种方法空间复杂度 k，不管数据量有多大，内存中占用不会变。总体的时间复杂度为：n * log(k)。 C++实现如下：

vector<int> maxTopKHeap(vector<int> &array, int k){
    unordered_map<int, bool> indexes;
    vector<int> heap;
    for(auto item: array){
        auto find = indexes.find(item);
        if (find != indexes.end())
            continue;

        if (heap.size() < k){
            indexes[item] = true;
            heap.push_back(item);
            push_heap(heap.begin(), heap.end(), greater<int>());
        }else{
            int top = heap[0];
            if (top < item){
                indexes.erase(top);
                indexes[item] = true;
                pop_heap(heap.begin(), heap.end(), greater<int>());
                heap.pop_back();
                heap.push_back(item);
                push_heap(heap.begin(), heap.end(), greater<int>());
            }
        }
    }
    return heap;
}
  • 使用快速选择算法(Quick Select)

使用这个算法需要内存够用，能把数据全部加载进来，且没有重复数据。

主要脱胎于快排中的 partition 函数。假设 partition划分的方法是比基准数据 大的在左边，小的在右边，那么：若一次划分返回的下标为 i，若 i==k，则说明找到了这K个数，若i>k，说明需要在左边去找，反之需要在右边去找，按照这个思路重复调用得到结果。

C++ 实现如下：

int partition(vector<int> &array, int start, int end){
    while (start < end){
        while(start < end && array[start] >= array[end]) --end;
        swap(array[start], array[end]);
        while(start < end && array[end] <= array[start]) ++start;
        swap(array[start], array[end]);
    }
    return start;
}

vector<int> maxTopKQuickSelect(vector<int> &array, int k){
    int index;
    int start = 0, end = array.size() - 1;
    while(true){
        index = partition(array, start, end);
        if (index == k)
            break;
        else if(index > k)
            end = index - 1;
        else
            start = index + 1;
    }
    vector<int> result(array.begin(), array.begin() + index);
    return result;
}

找重复次数最大的 K 个数

这个问题只能用分治法，因为需要统计数据出现的次数。

先将 n个数据分成 m 份，每一份 都找出重复次数最大的 K 个数，然后两两合并(2K)，在合并集合中 同样找重复次数最大的K个数，重复进行，最后的剩下的 K个数就是要的答案。