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

TopK 问题的类型

TopK 问题一般为海量数据问题,可以分为两种大类:

  • 找最大/最小的 K 个数

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

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

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

解决方法

找最大最小的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个数就是要的答案。

标签: 算法

添加新评论