• <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地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            99久久免费国产精品热| 伊人久久大香线焦综合四虎| 久久有码中文字幕| 久久婷婷色香五月综合激情| 超级碰碰碰碰97久久久久| 亚洲国产精品无码久久一区二区| 久久99国产综合精品| 国产精品成人精品久久久| 久久香综合精品久久伊人| 久久er99热精品一区二区| 久久99精品久久久久久齐齐| 亚洲国产精品无码成人片久久| 久久精品国产影库免费看 | 99国产欧美久久久精品蜜芽| 国产高清国内精品福利99久久| 精品久久久无码人妻中文字幕| 狠狠色丁香婷婷久久综合不卡| 欧美精品丝袜久久久中文字幕 | 亚洲精品国产美女久久久| 2021国产成人精品久久| 综合久久国产九一剧情麻豆| 国产成人99久久亚洲综合精品 | 久久99国产精品久久99小说| 久久中文娱乐网| 久久夜色精品国产噜噜噜亚洲AV| 免费精品久久久久久中文字幕| 久久99精品国产麻豆宅宅| 久久综合88熟人妻| 久久人人爽人人爽人人片AV不| 久久久无码精品亚洲日韩京东传媒 | 国产精品女同一区二区久久| 国产精品一区二区久久不卡| 久久久午夜精品| 久久亚洲精品国产精品婷婷| 久久伊人中文无码| 亚洲欧洲精品成人久久奇米网| 久久久久久国产a免费观看不卡 | 久久91亚洲人成电影网站| 97精品伊人久久大香线蕉app| 99久久超碰中文字幕伊人| 久久精品麻豆日日躁夜夜躁|