金华网站建设哪里好,wordpress 按钮,广州网站搭建快速提升网站排名,美容美发网站模板文章目录一、TopK问题是什么二、解决方法三、时间复杂度一、TopK问题是什么
TopK问题就是从1000个数中找出前K个最大的数或者最小的数这样的类似问题。
不过并不要求这k个数字必须是有序的#xff0c;如果题目有要求#xff0c;则进行堆排序即可。
还有比如求出全国玩韩信…
文章目录一、TopK问题是什么二、解决方法三、时间复杂度一、TopK问题是什么
TopK问题就是从1000个数中找出前K个最大的数或者最小的数这样的类似问题。
不过并不要求这k个数字必须是有序的如果题目有要求则进行堆排序即可。
还有比如求出全国玩韩信前十名等等排出班级前十名也是TopK问题。
二、解决方法
采用堆的方式可以较快解决。
思路如果需要排前k个最大的数则需要建一个小堆 如果需要排前k个最小的数则需要建一个大堆
假设现在需要排序前k个最大的数则需要建立一个小堆。 建立小堆是拿n个数的前k个数来建立的。
不能把n个数全部建立成一个小堆这样效率会大打折扣因为通过向下调整建堆的时间复杂度是O(N)假如要从10亿个数字中排前50个最大的那么建立一个10亿个数大小的堆开销还是比较大的。
建立了一个小堆后此时堆顶元素是最小的 从第k1个数开始只要第K1个数大于堆顶元素就将该数字于堆顶元素进行交换然后再向下调整。
这样做的结果是只要我比堆顶元素大我就进堆如果我在堆中是比较大的我就会“下沉”到堆底因为这是一个小堆。 这样遍历多次后原来堆中的元素会被换成新的一批更大一点的元素。
当我们遍历完n个数后留在堆中的一定是前k个最大的数。
代码如下 随机生成10个1000以内的数字求这10个数字的最大的3个
void Find_TopK(int* a, int n ,int k)
{assert(a!NULL);assert(k 0);int* topk (int*)malloc(sizeof(int) * k);assert(topk);for (int i 0; i k; i){topk[i] a[i];}//1.先建堆,向下调整建堆现在是建小堆那就找最大的前k个//把前k个抓起来建立一个k大小的堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(topk, k, i);}//2.然后从第k个开始往堆里面插入int j k;while (j n){if (a[j] topk[0]){topk[0] a[j];AdjustDown(topk, k, 0);}j;}printf(这10个数中最大的3个数为\n);for (int i 0; i k; i){printf(%d , topk[i]);}free(topk);topk NULL;
}int main()
{srand(time(0));int a[100] { 0 };printf(随机生成的10个1000以内的数为\n);for (int i 0; i 10; i){a[i] rand() % 1000;printf(%d , a[i]);}printf(\n);int k 3;int n sizeof(a) / sizeof(a[0]);Find_TopK(a,n,k);return 0;
}
三、时间复杂度
建堆的时间复杂度:O(K) 遍历的时间复杂度:O(N-K) 每次遍历调整的时间复杂度:O(logK) 总的时间复杂度O(K(N-K)logK) ≈ O(NlogK)
