<>TopK问题

 输入数组arr,找出其中最大的k个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最大的4个数字是5、6、7、8。
示例一:
 输入:arr = [3,2,1], k = 2
 输出:[3,2]或者[2,3]
示例二:
 输入:arr = [0,1,2,1], k = 1
 输出:[2]

<>境界一

代码如下:
//交换函数 void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }
//堆的向下调整(小堆) void AdjustDown(int* a, int n, int parent) {
//child记录左右孩子中值较小的孩子的下标 int child = 2 * parent + 1;//先默认其左孩子的值较小 while (child <
n) { if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小 { child++;
//较小的孩子改为右孩子 } if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小 { //将父结点与较小的子结点交换
Swap(&a[child], &a[parent]); //继续向下进行调整 parent = child; child = 2 * parent + 1;
} else//已成堆 { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k,
int* returnSize) { *returnSize = k; int i = 0; //建小堆 for (i = (arrSize - 1 - 1)
/ 2; i >= 0; i--) { AdjustDown(arr, arrSize, i); } //排降序 int end = arrSize - 1;
while (end > 0) { Swap(&arr[0], &arr[end]); AdjustDown(arr, end, 0); end--; }
//将最大的k个数存入数组 int* retArr = (int*)malloc(sizeof(int)*k); for (i = 0; i < k; i++)
{ retArr[i] = arr[i]; } return retArr;//返回最大的k个数 }
时间复杂度: O ( N + N l o g N ) O(N+NlogN) O(N+NlogN) 空间复杂度: O ( N ) O(N) O(N)

<>境界二

 要知道进行一次向下调整的时间复杂度为 O ( l o g N ) O(logN) O(logN),而进行一次建堆的时间复杂度为 O ( N ) O(N)
O(N)。

代码如下:
//交换函数 void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }
//堆的向下调整(大堆) void AdjustDown(int* a, int n, int parent) {
//child记录左右孩子中值较大的孩子的下标 int child = 2 * parent + 1;//先默认其左孩子的值较大 while (child <
n) { if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大 { child++;
//较大的孩子改为右孩子 } if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大 { //将父结点与较大的子结点交换
Swap(&a[child], &a[parent]); //继续向下进行调整 parent = child; child = 2 * parent + 1;
} else//已成堆 { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k,
int* returnSize) { *returnSize = k; int i = 0; //建大堆 for (i = (arrSize - 1 - 1)
/ 2; i >= 0; i--) { AdjustDown(arr, arrSize, i); } //将最大的k个数存入数组 int* retArr = (
int*)malloc(sizeof(int)*k); int end = arrSize - 1; for (i = 0; i < k; i++) {
retArr[i] = arr[0];//取堆顶数据 Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据
//进行一次向下调整,不把最后一个数据看作待调整的数据,所以待调整数据为end=arrSize-1 AdjustDown(arr, end, 0); end--
;//最后一个数据的下标改变 } return retArr;//返回最大的k个数 }
时间复杂度: O ( N + k l o g N ) O(N+klogN) O(N+klogN) 空间复杂度: O ( N ) O(N) O(N)

<>境界三

 存储100亿个整数究竟需要多大的内存空间?让咱们来大概估算一下:
 我们知道1KB=1024byte,1MB=1024KB,1GB=1024MB,于是可以得出1GB大概有230个字节,也就是说1GB大概等于10亿个字节。

 存储100亿个整型需要400亿个字节,所以存储100亿个整型数据需要40G左右的内存空间。前面两种算法的空间复杂度均为O(N),并不适合用于这种海量数据处理。

代码如下:
//交换函数 void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }
//堆的向下调整(小堆) void AdjustDown(int* a, int n, int parent) {
//child记录左右孩子中值较小的孩子的下标 int child = 2 * parent + 1;//先默认其左孩子的值较小 while (child <
n) { if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小 { child++;
//较小的孩子改为右孩子 } if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小 { //将父结点与较小的子结点交换
Swap(&a[child], &a[parent]); //继续向下进行调整 parent = child; child = 2 * parent + 1;
} else//已成堆 { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k,
int* returnSize) { *returnSize = k; if (k == 0) return NULL; //用数组的前K个数建小堆 int i
= 0; int* retArr = (int*)malloc(sizeof(int)*k); for (i = 0; i < k; i++) { retArr
[i] = arr[i]; } for (i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(retArr, k, i
); } //剩下的N-k个数依次与堆顶数据比较 for (i = k; i < arrSize; i++) { if (arr[i]>retArr[0]) {
retArr[0] = arr[i];//堆顶数据替换 } AdjustDown(retArr, k, 0);//进行一次向下调整 } return
retArr;//返回最大的k个数 }
时间复杂度: O ( k + N l o g k ) O(k+Nlogk) O(k+Nlogk) 空间复杂度: O ( k ) O(k) O(k)

技术
©2019-2020 Toolsou All rights reserved,
css中上下左右居中的几种实现方法[CISCN 2019 初赛]Love Mathc/c++语言实现登陆界面Unity3D 人称设置(第一人称视角、第三人称视角)Fastadmin框架自定义搜索操作流程2021最新Python自动化软件测试笔试题(含答案)黑客帝国装逼的代码雨mysql数据库设置字符集配置修改my.ini文件(windows)python之panda模块1Python学习笔记:基础+进阶10道练习题