付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0

题目:输入n个整数,输出其中最小的k个。
例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。

1 在数据量不大的情况下,排序

2 维护一个最小k 的数组 ,复杂度 为 o(k * N)

3 为一个最小K个数的最大堆 o(log2 k * N)

/*
查找最小的k 个元素
题目:输入n 个整数,输出其中最小的k 个。
例如输入1,2,3,4,5,6,7和8这8个数字,
则最小的4个数字为1,2,3和4。
*/

/*
思路 : 来一个数据处理一个 ,当来的数据量小于K 时 ,全部处理成最大堆,
        然后之后来的,必须要小于最大堆的的最大值,才可以入堆,此时 只需更新 根节点,再调整堆。

*/
# include<stdio.h>
# include<stdlib.h>
const int K = 5 ;//这里可以修改 
const int MAXN = 1000;

int max_heap[K+1] ;//维护一个 最大堆 
int end ,maxPos;


void swap(int &a ,int &b)
{
    int t = a;a = b ; b = t;
}


int FindMax()
{
    int maxPos = 1;
    for(int i = 2 ;i <= K ; i ++)
        if(max_heap[i] >max_heap[maxPos] )
            maxPos = i;
    return maxPos;
}
/*将数据插入到 数组中  插入排序的思想*/
void insertMinHeap(int mdata)
{
    int i,child = 0;
    if(end == K +1 ) // 如果堆满  
    {    
    /*    int mmaxPos = FindMax();*/
        if(mdata >= max_heap[1] ) // 如果大于等于该堆的最大值 不做任何改变
            return ;

        max_heap[1] = mdata;
        for(i = 1 ; i*2  <=  K ;i = child)
        {
            child = 2*i  ;
            if((i*2 +1 <= K && max_heap[i*2] < max_heap[i*2+1]) )//返回最大孩子的下表
                child ++;
            if(max_heap[i] < max_heap[child])
                swap(max_heap[i] ,max_heap[child]);
            else 
            {
                break;
            }
        }        
        return ;
    }

    max_heap[end ++] = mdata;
    for(i = end -1  ; i > 1 ; i /=2)
    {
        if(max_heap[i] > max_heap[i/2])
            swap(max_heap[i] ,max_heap[i/2]);
        else 
        {
            break;
        }
    }
    
}
int main()
{
    int n,data;
    freopen("in.txt","r",stdin);//如果想从文件输入 将这句注释掉 1234 1 2 3 4 5 6 7 8 9 10 11  
    end = 1;
    while(scanf("%d",&data)!=EOF) // 如果是手工输入 结束输入 按 ctrl + z
    {
        insertMinHeap(data);

    }
    
    for(int i = 1 ; i <= K ; i ++) // 
        printf("%d ",max_heap[i]);
    printf("\n");

    return 0;
}
posted on 2011-04-21 13:26 付翔 阅读(1225) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜