• <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>
            付翔的專欄
            在鄙視中成長 記錄成長的點滴
            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 付翔 閱讀(1297) 評論(0)  編輯 收藏 引用 所屬分類: ACM 數據結構

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

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久无码一区二区三区少妇| 国产成人精品三上悠亚久久| 精品一区二区久久久久久久网站| 久久国产精品一区二区| 国产999精品久久久久久| 久久久久99精品成人片三人毛片 | 久久综合精品国产二区无码| 午夜精品久久久久久中宇| 久久久久久久尹人综合网亚洲| 激情综合色综合久久综合| 伊人久久成人成综合网222| 麻豆一区二区99久久久久| 精品久久久久久久久久中文字幕 | 久久精品国产精品亚洲人人| 合区精品久久久中文字幕一区| 精品人妻伦九区久久AAA片69| 国产日产久久高清欧美一区| 亚洲精品国产综合久久一线| 久久线看观看精品香蕉国产| 一本一本久久a久久综合精品蜜桃| 久久播电影网| 久久不见久久见免费视频7| 热99RE久久精品这里都是精品免费| 久久成人影院精品777| 中文字幕久久久久人妻| 久久人人爽人爽人人爽av| 99久久国产综合精品五月天喷水| 久久久久久久久波多野高潮| 欧美午夜A∨大片久久| 久久天天躁狠狠躁夜夜2020一| 97久久综合精品久久久综合| 色综合久久综合中文综合网| 亚洲国产视频久久| 久久人人爽人人爽人人片AV麻豆| 久久国产精品-久久精品| 久久超乳爆乳中文字幕| 精品久久8x国产免费观看| 久久久久人妻一区二区三区vr | 欧美午夜精品久久久久免费视| 久久婷婷国产剧情内射白浆| 成人综合久久精品色婷婷|