成都购物网站设计,火车头采集Wordpress字段,建设积分网站,计算机应用是做什么的设计一个算法#xff0c;找出数组中最小的k个数。以任意顺序返回这k个数均可。
找小的数需要建大堆来解决#xff0c;首先将数组中前K个数建成一个大堆#xff0c;将从k1个数直到数组结束的所有数与堆顶的数进行比较#xff0c;如果比堆顶的数小#xff0c;则替换堆顶的数…设计一个算法找出数组中最小的k个数。以任意顺序返回这k个数均可。
找小的数需要建大堆来解决首先将数组中前K个数建成一个大堆将从k1个数直到数组结束的所有数与堆顶的数进行比较如果比堆顶的数小则替换堆顶的数据然后在向下调整重新形成一个新的大堆如果比堆顶的数小则不替换。以此循环直至数组k1个数到数组结束所有的数都比较完最后留在堆里的数就是最小的k个数。用题中的题目来说使用前4个数 1 3 5 7 来建一个大堆。 替换了之后由于不是一个大堆所以进行向下调整形成一个新的大堆。 替换了之后进行向下调整 最后输出的结果 #define _CRT_SECURE_NO_WARNINGS 1 #include stdio.h #include stdlib.h
void AdjustDown(int* a, int n, int root)//向下调整 { int parent root; int child parent * 2 1; while (child n) { if (child 1 n a[child 1] a[child])//选出大的那个孩子 { child; } if (a[child] a[parent]) { int tmp a[child]; a[child] a[parent]; a[parent] tmp; parent child; child parent * 2 1; } else { break; } } }
int* smallestK(int* arr, int arrSize, int k, int* returnSize) { *returnSize k; if (k 0) return NULL; int* retArr (int*)malloc(sizeof(int) * k); int i 0; for (i 0; i k; i) { retArr[i] arr[i]; } //建K个数的大堆 for (i (k - 1 - 1) / 2; i 0; i--) { AdjustDown(retArr, k, i); } for (i k; i arrSize; i) { if (arr[i] retArr[0]) { retArr[0] arr[i]; AdjustDown(retArr, k, 0); } } *returnSize k; return retArr; }
int main() { // 测试数据 int arr[] { 1,3,5,7,2,4,6,8 }; int arrSize sizeof(arr) / sizeof(arr[0]); int k 4; int returnSize; // 调用 smallestK 函数 int* result smallestK(arr, arrSize, k, returnSize); // 输出结果 printf(The smallest %d elements are:\n, k); for (int i 0; i returnSize; i) { printf(%d , result[i]); } printf(\n); // 释放分配的内存 free(result); return 0; }
