一周一算法—— TOPK算法

#技术 #算法

有一系列数据,是无序存在的,假设为n个,现在要从中取出其k个最大的数据,仅要求求出最大的k个,不需要 保证得到的k的数据为有序状态。

对于此类问题实际是经典的topk问题,在需要保持k个数据为有序状态时,可以通过建立一个大小为K的一个最大堆, 然后将数据依次输入最大堆,最后堆中最后存在的数据即为topK。而对于不需要保持k个数据有序的情况,则可以 利用快速排序的思想来完成。

    1.选取任意一个元素作为做分隔元素,将大于此元素的元素放于其前面,小于的放于后面。
    2.判断大于此元素的个数,若大于k则在前面部分继续步骤1,k不变; 若小于则在后面的部
      分继续完成步骤1的操作,k-前面部分元素的个数。
    3.直到最后k的值为0即退出。

算法求解的大致思想,即为上面所示,以下为代码实现:

    #include <stdio.h>
    #include <stdlib.h>

    #define NUMBER_CNT 20

    void topk(int a[], int n, int k) 
    {
        if ( k <= 0 ) {
            return ;
        }

        int t = a[0], j = 0, i =0;
        for (i = 1; i < n; i++) {
            if (a[i] > t) {
                a[i] = a[i] + a[j] -(a[j] = a[i]); 
                j++;
            }
        }
        j = j == 0 ? 1: j;
        if (j <= k) {
            topk(a + j , n - j, k - j);
        } else {
            topk(a, j, k);
        }
    }

    int main(int argc, char* argv[]) 
    {
        int a[NUMBER_CNT] = {101, 3, 5, 7, 3, 12, 54, 68, 54, 22, 0, 
                             23, 13, 99, 34, 26, 72, 73, 17, 19};

        int k = 5, i;
        topk(a, NUMBER_CNT, k);

        printf("Topk is: \n");
        for (i = 0; i < k; i ++) {
            printf("%d\t", a[i]);
        }
        printf("\n");
    }