解题思路:
用堆来解决这类问题十分合适。
如果直接将数组进行排序的话,显然不是很合理,因为可能会造成很大的浪费,比如要在10000个数中抽取1个数,而去大费周章把整个数组都给排了序,显然十分浪费电脑资源。因此只需要建个最小堆(小顶堆),让这个数组局部有序即可。
何为堆?
堆是一种特殊的二叉树,树的根的值是整棵树的最小值或者最大值(看这是棵什么树,小顶堆就是最小值),
左右子树也需要满足这一点,左子树的根是左子树中最大或者最小的,以此类推。
参考代码:
#include<cstdio> #include<malloc.h> #include<limits.h> using namespace std; void swap(int &a,int &b){ int temp=a; a=b; b=temp; } void PercDown(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--){ PercDown(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分
1 人评分
C语言程序设计教程(第三版)课后习题6.5 (Java代码)浏览:1122 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:525 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:435 |
简单的a+b (C语言代码)浏览:580 |
输入输出格式练习 (C语言代码)浏览:849 |
判定字符位置 (C语言代码)浏览:799 |
简单的事情 (C语言代码)浏览:638 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:540 |
C语言程序设计教程(第三版)课后习题8.4 (C++代码)浏览:458 |
数字统计 (C语言代码)浏览:1095 |