• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    6年前 (2012-09-25)  笔试面试 评论关闭  22 
    文章评分 0 次,平均分 0.0

    问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k或者Top 10)

    问题分析:由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。

    可以利用数据结构的最小堆来处理该问题。

    最小堆如图所示,对于每个非叶子节点的数值,一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数值)。

    每次有数据输入的时候可以先与根节点比较。若不大于根节点,则舍弃;否则用新数值替换根节点数值。并进行最小堆的调整。

    20173247-86b11c08bf4145c284b263b28215feef

    #include<stdio.h>
    int n;  ///数字个数,n很大(n>10000)
    int dui[10];
    #define K 10    ///Top K,K的取值
    
    void create_dui();  ///建堆
    void UpToDown(int);  ///从上到下调整
    int main()
    {
        int i;
        int tmp;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=1;i<=K;i++) ///先输入K个
                scanf("%d",&dui[i]);
            create_dui();  ///建小顶堆
            for(i=K+1;i<=n;i++)
            {
                scanf("%d",&tmp);
                if(tmp>dui[1])  ///只有大于根节点才处理
                {
                    dui[1]=tmp;
                    UpToDown(1);    ///向下调整堆
                }
            }
        }
        return 1;
    }
    
    void create_dui()
    {
        int i;
        int pos=K/2;      ///从末尾数,第一个非叶节点的位置K/2
        for(i=pos;i>=1;i--)
            UpToDown(i);
    }
    
    void UpToDown(int i)
    {
        int t1,t2,tmp,pos;
        t1=2*i; ///左孩子(存在的话)
        t2=t1+1;    ///右孩子(存在的话)
        if(t1>K)    ///无孩子节点
            return;
        else
        {
            if(t2>K)  ///只有左孩子
                pos=t1;
            else
                pos=dui[t1]>dui[t2]? t2:t1;
    
            if(dui[i]>dui[pos]) ///pos保存在子孩子中,数值较小者的位置
            {
                tmp=dui[i];dui[i]=dui[pos];dui[pos]=tmp;
                UpToDown(pos);
            }
        }
    }
     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/2156.html

    关于
    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享