作者wawi2 (@@)
看板C_and_CPP
標題[問題] Find the medium in the data stream
時間Fri Jan 27 00:11:13 2017
題目如同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
推 fatrabitree: counting sort? 01/27 01:06
→ FRAXIS: 1 的話用一個長度 100 的 array 作 count 就可以了吧 01/27 03:38
推 FRAXIS: 2 的話就額外紀錄不在 1 ~ 100 的數字就可以了 01/27 03:41
推 steve1012: 用一個vector reserve 100然後讀完以後回傳中點 01/27 05:51
→ wawi2: 看來counting sort的idea最好 01/28 05:00
→ JPChinbotsu: min max heap 01/29 00:48
→ wawi2: Min max heap在效能上會有問題 01/30 00:00