PTT數位生活區 / C_and_CPP (C/C++)

[問題] Find the medium in the data stream

看板C_and_CPP (C/C++)作者 (@@)時間9年前 (2017/01/27 00:11), 編輯推噓3(3推 0噓 4→)
留言7則, 5人參與, 最新討論串1/2 (看更多)
題目如同leetcode 295 https://leetcode.com/problems/find-median-from-data-stream/ 只需要使用有序的data structure(如set)跟一個iterator指向目前set中的medium 這樣就可以做到 不過我最近在準備面試時 看到有人遇到這題的follow ups 1. 如果確定資料都在1~100之間 可以怎麼改進? 2. 如果大部分的資料都在1~100之間 少數落在外面 又可以怎麼做? 請問各位有甚麼想法嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 100.12.182.66 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1485447077.A.C0B.html
推
01/27 01:06, , 1F
counting sort?
01/27 01:06, 1F
→
01/27 03:38, , 2F
1 的話用一個長度 100 的 array 作 count 就可以了吧
01/27 03:38, 2F
推
01/27 03:41, , 3F
2 的話就額外紀錄不在 1 ~ 100 的數字就可以了
01/27 03:41, 3F
推
01/27 05:51, , 4F
用一個vector reserve 100然後讀完以後回傳中點
01/27 05:51, 4F
→
01/28 05:00, , 5F
看來counting sort的idea最好
01/28 05:00, 5F
→
01/29 00:48, , 6F
min max heap
01/29 00:48, 6F
→
01/30 00:00, , 7F
Min max heap在效能上會有問題
01/30 00:00, 7F
‣ 更多 wawi2 的文章
文章代碼(AID): #1OYX-bmB (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 wawi2 的文章
文章代碼(AID): #1OYX-bmB (C_and_CPP)