}
### **🥐Ⅱ.**Top-K问题 💡**Top - K：** * 意思就是：求数据中`前K个`最大的元素或者最小的元素 * 比如：在高考出成绩时，需要对全省考生的成绩进行排序并取出前50名考生的成绩进行封锁，此时就涉及`Top-K`问题了 👉我们便以题目去理解它吧~ #### 🏷️最小的K个数【难度：简单】 🔍**题目传送门：** | [剑指 Offer 40. 最小的k个数](https://bbs.csdn.net/topics/618545628) | | --- | 输入整数数组 `arr` ，找出其中最小的 `k`个数 例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4 * **示例 1：** 输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
* **示例 2：** 输入：arr = [0,1,2,1], k = 1
输出：[0]
💡**解题关键：** 找出前`K`个最小的元素 ##### ➡️ 思路一：堆排序 * 利用我们刚刚所学的`堆排序`，对数组进行排序，然后取出前`K`个即可 ❗**特别注意：** * 我们需要自己先实现一个`堆排序`，再进行使用 * 在用完`堆`后，记得销毁，否则会造成`内存泄露` 👉**实现：** int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
int* returnArray = (int*)malloc(k * sizeof(int)) ;
HeadSort(arr,arrSize); for(int i = 0; i < k; i++) { returnArray[i] = arr[i]; } \*returnSize = k; return returnArray; }
> > 💫但目前`堆排序`的效率为： > > > > > O > > > ( > > > N > > > ∗ > > > l > > > o > > > g > > > N > > > ) > > > > O(N\*logN) > > > O(N∗logN)，是否还能优化呢？ > > > ⭐答案是可以的 > > > ##### ➡️ 思路二： 建堆 * 根据题意，我们只需要取出最小的前`K`个数即可，那我们便可以不对数组进行排序，而是利用`小堆`的特性：**每个父亲结点的值总是`≤`孩子结点的值** * 只需要对这个数组进行`建堆`（建成小堆）即可，然后每次都取出`根节点`（最小值），一共取`K`次，便是最小的前`K`个元素 ❗**特别注意：** * 我们需要自己先实现一个`堆`，再进行使用 👉**实现：** 1️⃣实现`堆` typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustDwon(HPDataType* a, int size, int parent);
void AdjustUp(HPDataType* a, int child);
void HeapDestroy(HP* php);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void HeapInit(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType\*)malloc(sizeof(HPDataType)\*n); if (php->a == NULL) { printf("malloc fail\n"); exit(-1); } //1.拷贝 memcpy(php->a, a, sizeof(HPDataType)\*n); php->size = n; php->capacity = n; //2.建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDwon(php->a, php->size, i); } }
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
void AdjustUp(HPDataType* a, int child)
{
int parent = (child – 1) / 2;
//while (parent >= 0)
while (child > 0)
{
//if (a[child] < a[parent])
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child – 1) / 2;
}
else
{
break;
}
}
}
//建小堆
void AdjustDwon(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
// 选出左右孩子中小/大的那个
if (child+1 < size && a[child+1] < a[child])
{
++child;
}
// 孩子跟父亲比较 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent \* 2 + 1; } else { break; } } }
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&(php->a[0]), &(php->a[php->size - 1])); php->size--; AdjustDwon(php->a, php->size, 0); }
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0]; }
2️⃣实现`Top-K` 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); } HeapDestroy(&hp); \*returnSize = k; return retArr; }
> > 💫但目前`堆`的效率为： > > > > > O > > > ( > > > N > > > + > > > k > > > ∗ > > > l > > > o > > > g > > > N > > > ) > > > > O(N + k\*logN) > > > O(N+k∗logN)，是否还能优化呢？ > > > ⭐答案是可以的 > > > ##### ➡️ 思路三： 建前K个数的堆 * 类似于`建堆`的操作，但不同的是，`建堆`是对数组内全部元素进行调整 * 但我们现在只需要针对前`K`个数进行建堆即可 ❗**特别注意：** * 找前`k`个最大的元素，则建`小堆` * 找前`k`个最小的元素，则建`大堆` 👉**步骤：** * 1️⃣用数据集合中前`K`个元素来建堆【因为这里需要找前`K`个最小的元素，所以建`大堆`】 * 2️⃣剩余的`N-K`个元素（`N`为总元素个数）依次与堆顶元素来比较，不满足则替换堆顶元素，再向下调整 * 3️⃣将剩余`N-K`个元素依次与堆顶元素比完之后，堆中剩余的`K`个元素就是所求的前`K`个最小或者最大的元素 【我们现在这里建的是`大堆`，如果与堆顶元素比较时，外面的某个元素`小于`堆顶的值，则为不满足】 ❗**特别注意：** * 🔴本质：通过数组剩下的`N-K`个元素，找到比前`K`个元素的堆中的`堆顶`元素小的元素，进行轮换 + 1️⃣即在剩下的元素中，找到比堆顶还小的元素，不断轮换`堆`中元素的最大值 + 2️⃣因为要找的是最小的`K`个元素，所以最小的前`K`个一定比`大堆堆顶`的数据小，一定可以进堆中 * 🟡这也是为什么建`大堆`的原因，保证前`K`个最小的元素中的最小值进来一定不会在`堆顶`位置（以防前`K`个最小的元素中的最大值进不来） * 🔵现在即使是前`K`个最小的元素中的最大值进堆，那`前K-1`个最小的元素还是依然可以进堆 * 🟣直至这`K`个数据的堆不再进入元素，说明此时堆内的`K`个数据就是前`K`个最小的元素【堆外面没有比这`K`个元素更小的数了】 ⭐**亮点：** * 1️⃣在面对大量数据且无论多大的时候，需要解决`Top-K`问题时，这个方法依然受用，因为我们始终是在维护一个`K`个数的堆【只需要遍历剩下的元素进行比较、进堆、向下调整而已】 * 2️⃣此方法的**时间复杂度**始终为： O ( ( N − K ) ∗ l o g K ) O((N-K )\*logK) O((N−K)∗logK) + 这是因为需要遍历`N-K` 个元素与堆顶元素进行比较 + 若不满足进堆后，需要向下调整（有`K`个元素进行向下调整）【 O ( l o g k ) O(logk) O(logk)】 * 3️⃣此方法的**空间复杂度**为： O ( K ) O(K) O(K) ✊**动图示例：** > >  > > > 👉**实现：** 1️⃣实现`建堆` void Swap(HPDataType* p1, HPDataType* p2);
void AdjustDwon(HPDataType* a, int size, int parent);
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//建大堆
void AdjustDwon(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
// 选出左右孩子中小/大的那个
if (child+1 < size && a[child+1] > a[child])
{
++child;
}
// 孩子跟父亲比较 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent \* 2 + 1; } else { break; } } }
2️⃣实现`Top-K` 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个最小 -- 前k个数建大堆 for(int i = 0; i < k; i++) { arrRet[i] = arr[i]; } for(int j = (k-1-1) / 2; j >= 0; j--) { AdjustDwon(arrRet,k,j); } //剩下的N-K个数，比堆顶小的，就替换堆顶数据，进堆调整 for(int l=k;l<arrSize; l++) { if(arr[l] < arrRet[0]) { arrRet[0] = arr[l]; AdjustDwon(arrRet, k, 0); } } 
网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。
一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
= (k-1-1) / 2; j >= 0; j–)
{
AdjustDwon(arrRet,k,j);
}
//剩下的N-K个数，比堆顶小的，就替换堆顶数据，进堆调整 for(int l=k;l<arrSize; l++) { if(arr[l] < arrRet[0]) { arrRet[0] = arr[l]; AdjustDwon(arrRet, k, 0); } } [外链图片转存中…(img-F4lLpaz1-1714635822938)]
[外链图片转存中…(img-6f6sgeCp-1714635822938)]
网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。
一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
原文链接：https://blog.csdn.net/2401_84181403/article/details/138393373?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171910766916800215073550%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=171910766916800215073550&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~times_rank-28-138393373-null-null.nonecase&utm_term=2024%E9%AB%98%E8%80%83%E6%88%90%E7%BB%A9
