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

付翔的專欄
在鄙視中成長 記錄成長的點滴
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>
            亚洲欧美在线一区二区| 99精品热6080yy久久| 久久国产综合精品| 在线观看一区二区视频| 欧美不卡在线视频| 欧美福利一区二区三区| 亚洲天天影视| 欧美一区二区三区免费视频| 极品裸体白嫩激情啪啪国产精品| 欧美国产日韩二区| 欧美日韩激情小视频| 欧美与欧洲交xxxx免费观看 | 艳女tv在线观看国产一区| 亚洲另类黄色| 国产亚洲女人久久久久毛片| 欧美成人精品在线视频| 欧美日韩一区二区三| 午夜欧美大尺度福利影院在线看| 久久国产精品久久久久久久久久| 亚洲人精品午夜| 亚洲一区日韩| 亚洲精品一区二区三区四区高清| 亚洲一区二区三区精品在线观看 | 国产亚洲欧美日韩日本| 亚洲国产cao| 国产偷自视频区视频一区二区| 久久阴道视频| 欧美四级电影网站| 欧美不卡一区| 国产日韩欧美| 一区二区三区日韩在线观看| 亚洲国产91色在线| 亚洲欧美高清| 亚洲天堂激情| 欧美高清视频一二三区| 久久久久久久久久看片| 国产精品成av人在线视午夜片| 男同欧美伦乱| 国产主播在线一区| 一区二区免费在线观看| 91久久国产综合久久| 久久不射中文字幕| 欧美亚洲尤物久久| 国产精品v一区二区三区| 亚洲电影网站| 亚洲黄色免费| 久久综合九色综合欧美狠狠| 久久精品国产精品亚洲精品| 国产精品福利久久久| 亚洲啪啪91| 亚洲欧洲综合另类在线| 快she精品国产999| 久久亚洲二区| 狠狠色狠色综合曰曰| 午夜电影亚洲| 欧美在线视频免费播放| 国产精品天天摸av网| 一区二区高清| 亚洲欧美一区二区激情| 欧美体内谢she精2性欧美| 亚洲看片一区| 亚洲一区二区三区四区视频| 欧美日韩国产综合视频在线| 亚洲精品久久久久| 这里只有精品丝袜| 国产精品美女久久| 亚洲一区二区免费视频| 欧美一级久久| 国产一区二区三区最好精华液| 性做久久久久久久免费看| 久久精品亚洲精品国产欧美kt∨| 国产视频久久久久| 久久久久久久一区二区| 欧美激情第9页| 亚洲国产欧美另类丝袜| 欧美精品色综合| 中文欧美在线视频| 久久精品欧美| 亚洲观看高清完整版在线观看| 欧美99久久| 一个色综合av| 久久精品在线视频| 亚洲激情校园春色| 国产精品成人v| 欧美在线999| 亚洲国产精品ⅴa在线观看 | 国产欧美日韩精品丝袜高跟鞋 | 免播放器亚洲一区| 日韩午夜激情电影| 久久国产黑丝| 亚洲欧洲偷拍精品| 国产精品成人一区二区三区夜夜夜 | 国产日韩成人精品| 老司机午夜精品视频| 日韩一级成人av| 久久精品日韩欧美| 99精品视频一区| 国产色产综合产在线视频| 久久综合久色欧美综合狠狠| 一本色道**综合亚洲精品蜜桃冫| 久久岛国电影| 在线亚洲一区二区| 好吊一区二区三区| 欧美日一区二区在线观看| 久久精品亚洲一区二区三区浴池| 亚洲精品一区二区三区四区高清 | 久久久国产成人精品| 日韩视频专区| 狠狠干成人综合网| 欧美无砖砖区免费| 欧美成人免费va影院高清| 亚洲欧美一区二区三区久久| 亚洲高清在线观看| 久久综合中文字幕| 性做久久久久久久免费看| 亚洲乱码国产乱码精品精98午夜| 国产无一区二区| 欧美日韩美女在线| 欧美大片一区| 久久久久久亚洲精品不卡4k岛国| 中文一区二区在线观看| 亚洲国产天堂网精品网站| 久久亚洲精选| 欧美与黑人午夜性猛交久久久| 中文欧美字幕免费| 亚洲精品美女久久久久| 在线观看亚洲视频| 激情亚洲网站| 狠狠久久亚洲欧美专区| 国产亚洲欧美在线| 国产精品一卡二卡| 国产精品美女久久福利网站| 欧美三级日本三级少妇99| 欧美精品免费观看二区| 欧美成人一区二区| 欧美xx69| 欧美国产日韩精品| 欧美国产免费| 欧美国产第二页| 欧美国产国产综合| 欧美精品一级| 欧美日韩aaaaa| 欧美日韩一区二| 欧美日韩中文字幕日韩欧美| 欧美日韩理论| 国产精品美女久久久久久久 | 欧美日韩精品中文字幕| 欧美日韩午夜剧场| 欧美日韩在线视频首页| 欧美性久久久| 国产视频精品免费播放| 国内精品视频666| 亚洲国产精品久久| 亚洲看片免费| 亚洲一区二区黄色| 欧美一区91| 久久在线免费观看视频| 美国三级日本三级久久99| 欧美高清视频免费观看| 亚洲麻豆av| 午夜亚洲伦理| 欧美91大片| 国产精品久久久久一区二区三区 | 一区二区在线视频观看| 亚洲国产cao| 亚洲午夜精品久久| 久久国产99| 亚洲国产精品久久久久秋霞不卡| 亚洲精品视频二区| 欧美一区二区日韩| 欧美成人日韩| 国产精品自拍三区| 亚洲国产精品成人久久综合一区| 一区二区三区毛片| 久久久久国产免费免费| 91久久精品日日躁夜夜躁欧美| 在线一区二区三区四区| 久久久国产91| 国产精品黄页免费高清在线观看| 影音欧美亚洲| 午夜国产欧美理论在线播放| 欧美va亚洲va日韩∨a综合色| 99国产精品自拍| 久久久久久久综合| 国产精品任我爽爆在线播放 | 国产精品高潮呻吟久久| 伊人色综合久久天天五月婷| 亚洲视频1区2区| 欧美成人午夜影院| 午夜精品亚洲| 欧美三级不卡| 亚洲国产精品999| 久久不射2019中文字幕| 亚洲精品永久免费精品| 久久午夜视频| 国户精品久久久久久久久久久不卡| 99v久久综合狠狠综合久久| 免费日韩成人| 欧美综合激情网| 国产精品自拍一区|