解题思路:
用堆来解决这类问题十分合适。
如果直接将数组进行排序的话,显然不是很合理,因为可能会造成很大的浪费,比如要在10000个数中抽取1个数,而去大费周章把整个数组都给排了序,显然十分浪费电脑资源。因此只需要建个最小堆(小顶堆),让这个数组局部有序即可。
何为堆?
堆是一种特殊的二叉树,树的根的值是整棵树的最小值或者最大值(看这是棵什么树,小顶堆就是最小值),
左右子树也需要满足这一点,左子树的根是左子树中最大或者最小的,以此类推。
参考代码:
#include<stdio.h>
#include<malloc.h>
#include<limits.h>
void swap(int *a,int *b){
int temp=*a;
*a=*b;
*b=temp;
}
void PercUp(int* array,int size,int loc){//上滤
int parent,child;
for(parent=loc;parent*2+1<size;parent=child){
child=parent*2+1;
if(child+1<size&&array[child]>array[child+1])
child++;//如果当前位置parent有两个孩子,找出值最小的那个孩子
if(array[parent]>array[child]){
//如果parent的值大于孩子的值,则将它调整为小顶堆
swap(&array[parent],&array[child]);
}else{
//如果parent的值比孩子的值小,则已经是小顶堆
return;
}
}
}
void buildMinHeap(int* array,int size){
for(int temp=size/2;temp>=0;temp--){
PercUp(array,size,temp);
}
}
void printMin(int *array,int size){
buildMinHeap(array,size);
printf("%d ",array[0]);
array[0]=INT_MAX;
}
int main(){
int size,num;
scanf("%d%d",&size,&num);
int* array=(int*)malloc(size*sizeof(int));
for(int i=0;i<size;i++)
scanf("%d",&array[i]);
for(int i=0;i<num;i++)
printMin(array,size);
return 0;
}
0.0分
6 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:556 |
C语言程序设计教程(第三版)课后习题9.8 (Java代码)浏览:1640 |
WU-陶陶摘苹果2 (C++代码)浏览:973 |
Hello, world! (C语言代码)浏览:714 |
核桃的数量 (C语言代码)浏览:872 |
C二级辅导-阶乘数列 (C语言代码)浏览:520 |
剪刀石头布 (C语言代码)浏览:1436 |
陶陶摘苹果2 (C语言代码)浏览:601 |
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:610 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:699 |