[問題] 找出最小的10個值

[harristime (瀚宇)]

開發平台(Platform): Linux


問題(Question): 一個執行500次的while loop,
                     每跑一次會得到一個值a,
                     如何在這500個"a"內找出最小的10個值呢?

                     謝謝

程式碼(Code)：

             Ex:
                int a = 0;

                while(c < 500)
                {
                    get_xxx(&a);
                        .
                        .
                        .
                    c++;
                }

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 1.169.163.228
→ stupid0319:把500個值由小到大排,前10個不就是了= =
推 EdisonX:除了排序, 應有更快的方法..
→ loveme00835:建一個大小為 10 的 priority queue, 只跟其中最大的
→ loveme00835:比, 小於它才加入其中
→ loveme00835:你的 queue 結構影響執行效率, 如果有 N筆資料那複雜
→ loveme00835:度最快應可以到 O(N)
→ leiyan:用hash做的時候就排應該比較快
→ chunhsiang:要不然用10個大小的array 每次打最大那個取代也差不多
→ chunhsiang:同樓上O(n)
→ chunhsiang:如果是取m個最小的 那priority queue會好
推 EdisonX:c 大前面的方法似乎有點暇疵，10個array初值如何決定 ?
→ loveme00835:std::numeric_limits<T>::min()
→ EdisonX:sorry, array 方法是可以的無誤.
→ loveme00835:話說我好像打相反 wwwww
推 alongalone:可以traversal的話,按大小建binary tree,DFS前10個
→ enthos:http://en.wikipedia.org/wiki/Selection_algorithm