Top k | 酒招旗风中萧萧
Cobb 644 1

Top k 问题:求出一组数据中最大或最小的前K个元素

方法一: 小根堆(最小堆)求Top k 大的 大根堆(最大堆)求Top k 小的

方法二:快排分割 思路: // 0.1、 对序列进行快排分割笑操作,获取基准数位置pos // 0.2、 比较pos和k的值(递归) // pos == k-1 0 -- (k-1) 就是Top k 最小的哪些数组 // pos > k-1 在pos的左边范围继续重复上面操作 // pos < k-1 在pos的右边范围继续重复上面操作



#include <iostream>
#include <time.h>

/*
* 函数功能: 快排分割
* 作用: 利用快排分割,求top K 问题
* 返回值: 下一次的分割线 pos
*/
int Partation(int arr[], int i, int j, int ret = true)
{
    int val = arr[i];

    while (i < j)
    {
        //  用户不判断就是默认从小到大排列
        if (ret)
        {
            while (i < j && arr[j] >= val)
            {
                j--;
            }
            if (i < j)
            {
                arr[i] = arr[j];
                i++;
            }

            while (i < j && arr[i] < val)
            {
                i++;
            }
            if (i < j)
            {
                arr[j] = arr[i];
                j--;
            }

        }
        else // 用户选择了以后就是 从 大到小排序
        {
            while (i < j && arr[j] <= val)
            {
                j--;
            }
            if (i < j)
            {
                arr[i] = arr[j];
                i++;
            }

            while (i < j && arr[i] > val)
            {
                i++;
            }
            if (i < j)
            {
                arr[j] = arr[i];
                j--;
            }
        }
    }

    arr[i] = val;
    return i;
}



/*
* 函数功能: 找top k
* 思路: 先利用快排分割,找到分割点。 利用递归,找到前K个元素
*/
int SelectTopK (int arr[], int i, int j, int k, int ret = true)
{
    // 1、未找到,递归结束
    if (i > j)
    {
        return -1;
    }

    // 2、找到了,递归结束
    int pos = Partation(arr, i, j, ret);
    if (pos == k - 1)
    {
        return pos;
    }
    else if (pos > k - 1)
    {
        return SelectTopK(arr, i, pos - 1, k);
    }
    else
    {
         return SelectTopK(arr, pos + 1, j, k);
    }
}


int main()
{
    // true 小 -> 大 (默认)
    // false 大 -> 小
    srand(time(0));
    int *p = (int*)malloc(sizeof(int) * 100);

    for (int i = 0; i < 100; i++)
    {
        p[i] = rand() % 1000;
    }

    // 小 -> 大
    int pos = SelectTopK(p, 0, 99, 10, true);
    for (int i = 0; i <= pos; i++)
    {
        printf("%d ", p[i]);
    }
    printf("\n");

    // 大 -> 小
    int Pos = SelectTopK(p, 0, 99, 10, false);
    for (int i = 0; i <= Pos; i++)
    {
        printf("%d ", p[i]);
    }
    printf("\n");
}
评论区