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

看板C_and_CPP作者 (瀚宇)時間13年前 (2012/05/10 22:50), 編輯推噓3(3013)
留言16則, 7人參與, 最新討論串1/2 (看更多)
開發平台(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

05/10 22:53, , 1F
把500個值由小到大排,前10個不就是了= =
05/10 22:53, 1F

05/10 22:56, , 2F
除了排序, 應有更快的方法..
05/10 22:56, 2F

05/10 22:59, , 3F
建一個大小為 10 的 priority queue, 只跟其中最大的
05/10 22:59, 3F

05/10 23:00, , 4F
比, 小於它才加入其中
05/10 23:00, 4F

05/10 23:01, , 5F
你的 queue 結構影響執行效率, 如果有 N筆資料那複雜
05/10 23:01, 5F

05/10 23:01, , 6F
度最快應可以到 O(N)
05/10 23:01, 6F

05/10 23:05, , 7F
用hash做的時候就排應該比較快
05/10 23:05, 7F

05/10 23:06, , 8F
要不然用10個大小的array 每次打最大那個取代也差不多
05/10 23:06, 8F

05/10 23:08, , 9F
同樓上O(n)
05/10 23:08, 9F

05/10 23:09, , 10F
如果是取m個最小的 那priority queue會好
05/10 23:09, 10F

05/10 23:33, , 11F
c 大前面的方法似乎有點暇疵,10個array初值如何決定 ?
05/10 23:33, 11F

05/10 23:45, , 12F
std::numeric_limits<T>::min()
05/10 23:45, 12F

05/10 23:46, , 13F
sorry, array 方法是可以的無誤.
05/10 23:46, 13F

05/11 00:23, , 14F
話說我好像打相反 wwwww
05/11 00:23, 14F

05/11 16:29, , 15F
可以traversal的話,按大小建binary tree,DFS前10個
05/11 16:29, 15F

文章代碼(AID): #1FgzMqmp (C_and_CPP)
文章代碼(AID): #1FgzMqmp (C_and_CPP)