TOP-K在题中的应用
题目描述：（题目来源：力扣）
思路1：排序0(N*logN)
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
HP hp;
HeapInit(&hp,arr,arrsize);
int* retarr = (int*)malloc(sizeof(int)*k);
for(int i = 0;i < k;i++)
{
retarr[i] = HeapTop(&hp);
HeapPop(&hp);
}
HeapDestory(&hp);
*returnSize = k;
return retarr;
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
要求再提高效率
思路二（TOP-K）：
把N个数建成小堆，选一个删一个，不断选出前K个最小的
**时间复杂度：O(N+O(logN*K)) **
空间复杂度 O(N)
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
if(k == 0)
{
*returnSize = 0;
return NULL;
}
int* arrRet = (int*)malloc(sizeof(int)*k);
//前K个数建立大堆
for(int i = 0;i < k;i++)
{
arrRet[i] = arr[i];
}
for(int j = (k-1-1)/2;j >= 0;j--)
{
AdjusDown(arrRet,k,j);
}
//剩下的N-K个数，比堆顶小，就替换堆顶数，进堆
for(int i = k;i< arrSize;i++)
{
if(arr[i] < arrRet[0])
{
arrRet[0] = arr[i];
AdjusDown(arrRet,k,0);
}
}
*returnSize = k;
return arrRet;
}
衍生问题：假设N是100亿，K是100
100亿个整数需要多少空间？
1KB = 1024byte
1MB = 1024KB
1GB = 1024MB
1GB = 2^30
大概40GB左右
(注：代码中的函数在另一篇文章中实现：建堆)
