青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

付翔的專欄
在鄙視中成長 記錄成長的點滴
posts - 106,  comments - 32,  trackbacks - 0

題目:輸入n個整數(shù),輸出其中最小的k個。
例如輸入1,2,3,4,5,6,7和8這8個數(shù)字,則最小的4個數(shù)字為1,2,3和4。

1 在數(shù)據(jù)量不大的情況下,排序

2 維護(hù)一個最小k 的數(shù)組 ,復(fù)雜度 為 o(k * N)

3 為一個最小K個數(shù)的最大堆 o(log2 k * N)

/*
查找最小的k 個元素
題目:輸入n 個整數(shù),輸出其中最小的k 個。
例如輸入1,2,3,4,5,6,7和8這8個數(shù)字,
則最小的4個數(shù)字為1,2,3和4。
*/

/*
思路 : 來一個數(shù)據(jù)處理一個 ,當(dāng)來的數(shù)據(jù)量小于K 時 ,全部處理成最大堆,
        然后之后來的,必須要小于最大堆的的最大值,才可以入堆,此時 只需更新 根節(jié)點,再調(diào)整堆。

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

int max_heap[K+1] ;//維護(hù)一個 最大堆 
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;
}
/*將數(shù)據(jù)插入到 數(shù)組中  插入排序的思想*/
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) // 如果是手工輸入 結(jié)束輸入 按 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 付翔 閱讀(1307) 評論(0)  編輯 收藏 引用 所屬分類: ACM 數(shù)據(jù)結(jié)構(gòu)

<2011年1月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

常用鏈接

留言簿(2)

隨筆分類

隨筆檔案

文章分類

文章檔案

CSDN - 我的blog地址

博客

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            在线观看视频一区二区欧美日韩| 国产亚洲va综合人人澡精品| 亚洲国产综合在线| 欧美激情国产精品| 欧美激情视频网站| 亚洲欧美一区二区在线观看| 香港成人在线视频| 亚洲国产一区二区三区青草影视| 亚洲欧洲精品成人久久奇米网| 欧美电影电视剧在线观看| 亚洲精品免费电影| 亚洲一级片在线观看| 影院欧美亚洲| 亚洲精品综合| 国产综合色产在线精品| 欧美激情亚洲综合一区| 国产精品成人免费视频 | 欧美精品乱人伦久久久久久 | 亚洲国产精品久久久久秋霞蜜臀| 亚洲国产一区二区在线| 牛人盗摄一区二区三区视频| 美脚丝袜一区二区三区在线观看| 亚洲深夜福利| 久久久久国产成人精品亚洲午夜| 一本一本大道香蕉久在线精品| 亚洲综合日韩在线| 亚洲美女毛片| 久久aⅴ国产欧美74aaa| 国产精品99久久久久久久久久久久| 先锋资源久久| 亚洲午夜久久久久久久久电影网| 久久九九国产精品| 性欧美办公室18xxxxhd| 欧美激情网友自拍| 另类天堂视频在线观看| 国产精品久久久久久久久借妻| 亚洲大胆视频| 尤物网精品视频| 亚洲在线成人| 99视频精品全国免费| 久久久久久亚洲精品杨幂换脸| 午夜精品国产精品大乳美女| 欧美丰满高潮xxxx喷水动漫| 久久精品91久久久久久再现| 欧美网站在线观看| 国产亚洲精品久久飘花| 亚洲欧洲在线观看| 亚洲激情二区| 老牛国产精品一区的观看方式| 久久国产精品亚洲77777| 国产精品成人一区二区网站软件| 亚洲人在线视频| 亚洲国产日韩一区| 久久综合亚洲社区| 葵司免费一区二区三区四区五区| 国产欧美日韩视频在线观看| 亚洲图中文字幕| 亚洲男同1069视频| 国产精品黄色| 亚洲一级片在线看| 欧美伊人久久| 国产一区二区三区四区在线观看| 亚洲男人的天堂在线观看| 亚洲欧美在线高清| 国产精品亚洲激情| 午夜老司机精品| 久久婷婷久久| 亚洲国产cao| 欧美精品久久久久久久久老牛影院 | 制服丝袜亚洲播放| 亚洲欧美韩国| 国产一区二区精品久久99| 欧美一区二区三区视频免费播放| 久久久久免费视频| 伊大人香蕉综合8在线视| 久久久蜜臀国产一区二区| 欧美国内亚洲| 99国产精品久久久久久久| 欧美日韩中文| 午夜一级久久| 欧美好吊妞视频| 亚洲伊人一本大道中文字幕| 国产精品亚洲人在线观看| 欧美一区二区三区播放老司机| 开心色5月久久精品| 亚洲精品美女在线观看播放| 欧美日韩午夜| 欧美在线视频一区二区| 欧美大片一区二区三区| 亚洲影院在线| 在线不卡欧美| 欧美日韩中文| 久久天堂av综合合色| 亚洲精品一区二区三区樱花 | 亚洲综合色自拍一区| 好吊色欧美一区二区三区四区| 欧美v亚洲v综合ⅴ国产v| 99精品久久免费看蜜臀剧情介绍| 欧美在线视频一区二区| 亚洲精品久久久久久久久久久久 | 欧美一站二站| 亚洲精品极品| 久热国产精品| 亚洲欧美电影院| 亚洲国产成人精品视频| 国产精品一区二区久久精品| 六月天综合网| 欧美亚洲在线观看| 一区二区三区四区五区精品| 欧美国产精品人人做人人爱| 翔田千里一区二区| 一本色道久久88精品综合| 国产在线观看精品一区二区三区| 欧美激情bt| 久久亚洲精品欧美| 午夜电影亚洲| 在线一区日本视频| 亚洲区欧美区| 欧美视频在线视频| 欧美成人免费播放| 久久久久国产一区二区三区四区 | 久久久免费观看视频| 亚洲宅男天堂在线观看无病毒| 亚洲激情视频网站| 欧美激情亚洲激情| 美女网站在线免费欧美精品| 久久国产视频网站| 亚洲综合国产激情另类一区| 一区二区三区日韩在线观看| 亚洲区一区二| 亚洲人成在线观看一区二区| 很黄很黄激情成人| 精品91在线| 黄色亚洲在线| 一区二区三区在线不卡| 国产一区二区激情| 黑人巨大精品欧美一区二区小视频| 国产女人精品视频| 国产女精品视频网站免费| 国产欧美日韩视频在线观看| 国产伦精品一区二区三区视频孕妇| 国产精品久久久久9999| 国产精品日韩在线一区| 国产精品婷婷午夜在线观看| 国产精品影片在线观看| 国产九九视频一区二区三区| 国产日产欧产精品推荐色| 国产亚洲欧美日韩一区二区| 国产亚洲美州欧州综合国| 国产综合久久| 亚洲国产欧洲综合997久久| 亚洲精品一品区二品区三品区| 91久久一区二区| 一本色道久久88亚洲综合88 | 国产婷婷色一区二区三区在线| 国产欧美欧洲在线观看| 国内视频一区| 亚洲人成网在线播放| 亚洲一区二区三区国产| 欧美一级精品大片| 麻豆久久婷婷| 亚洲麻豆av| 午夜精品久久久久久久99樱桃 | 亚洲欧美日韩国产一区二区| 久久爱www久久做| 欧美国产日韩免费| 国产精品日韩精品| 伊人久久男人天堂| 99精品99| 久久午夜激情| 日韩午夜精品视频| 久久精品国产欧美激情| 欧美激情在线免费观看| 国产美女精品视频免费观看| 亚洲国产精品v| 亚洲免费视频观看| 欧美成人综合| 亚洲永久精品大片| 欧美激情第3页| 国产综合色产在线精品| 制服丝袜激情欧洲亚洲| 久热国产精品视频| 亚洲午夜在线视频| 蜜桃av一区二区三区| 国产欧美日韩综合一区在线观看| 亚洲国产精品一区二区www在线| 午夜国产精品影院在线观看| 欧美大片免费观看在线观看网站推荐 | 亚洲精品国产精品国产自| 欧美一级在线视频| 免费中文日韩| 亚洲免费网站| 欧美日韩国产不卡| 亚洲高清视频中文字幕| 午夜一区在线| 日韩午夜av在线| 欧美第十八页| 91久久精品一区| 欧美11—12娇小xxxx| 久久成人资源|