作者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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1485447077.A.C0B.html
1F:推 fatrabitree: counting sort? 01/27 01:06
2F:→ FRAXIS: 1 的话用一个长度 100 的 array 作 count 就可以了吧 01/27 03:38
3F:推 FRAXIS: 2 的话就额外纪录不在 1 ~ 100 的数字就可以了 01/27 03:41
4F:推 steve1012: 用一个vector reserve 100然後读完以後回传中点 01/27 05:51
5F:→ wawi2: 看来counting sort的idea最好 01/28 05:00
6F:→ JPChinbotsu: min max heap 01/29 00:48
7F:→ wawi2: Min max heap在效能上会有问题 01/30 00:00