e*****m
发帖数: 320 | 1 不是面试题，而是实际工作中遇到的一个问题。本人不怎么懂算法，向版上大牛们请教：
有一个实时采集的数列，想随时更新最后采集的N个数的中位数，但又不保存（至少不
全部保存）这N个数。请问这个问题可行么？
也就是想实时计算最后一段时间采集的数据的中位数，但是由于条件限制不能全部保存
所有数据。
多谢！ |
l*********8
发帖数: 4642 | 2 保存最后N个数字的histogram可以吗？
教：
【在 e*****m 的大作中提到】
: 不是面试题，而是实际工作中遇到的一个问题。本人不怎么懂算法，向版上大牛们请教：
: 有一个实时采集的数列，想随时更新最后采集的N个数的中位数，但又不保存（至少不
: 全部保存）这N个数。请问这个问题可行么？
: 也就是想实时计算最后一段时间采集的数据的中位数，但是由于条件限制不能全部保存
: 所有数据。
: 多谢！
|
e*****m
发帖数: 320 | 3 我不是码工，不是特别明白你的意思，能否展开说说？多谢！
【在 l*********8 的大作中提到】
: 保存最后N个数字的histogram可以吗？
:
: 教：
|
l*********8
发帖数: 4642 | 4 比如N = 10。
最后10个数是： 2 3 2 8 8 2 8 10 3 10
那么就保存为 2=>3(2出现了3次), 3=>2, 8=>3, 10=>2
【在 e*****m 的大作中提到】
: 我不是码工，不是特别明白你的意思，能否展开说说？多谢！
|
e*****m
发帖数: 320 | 5 哦哦。。。问题是新进来的数在HISTGRAM上＋1就可以了，挤出去的那个数的频数怎么
更新？
【在 l*********8 的大作中提到】
: 比如N = 10。
: 最后10个数是： 2 3 2 8 8 2 8 10 3 10
: 那么就保存为 2=>3(2出现了3次), 3=>2, 8=>3, 10=>2
|
l*********8
发帖数: 4642 | 6 如果把2挤出去，就把2的count减一。
【在 e*****m 的大作中提到】
: 哦哦。。。问题是新进来的数在HISTGRAM上＋1就可以了，挤出去的那个数的频数怎么
: 更新？
|
e*****m
发帖数: 320 | 7 麻烦就是在这里：由于环境的限制无法保存所有的数，所以不知道马上要被挤出去的数
是什么。
【在 l*********8 的大作中提到】
: 如果把2挤出去，就把2的count减一。
|
l*********8
发帖数: 4642 | 8 唉，是啊。。。。我再想想
【在 e*****m 的大作中提到】
: 麻烦就是在这里：由于环境的限制无法保存所有的数，所以不知道马上要被挤出去的数
: 是什么。
|
p**o
发帖数: 3409 | 9 设m为N个数里unique的数的个数，你的m/N的概率密度函数大致长什么样？
教：
【在 e*****m 的大作中提到】
: 不是面试题，而是实际工作中遇到的一个问题。本人不怎么懂算法，向版上大牛们请教：
: 有一个实时采集的数列，想随时更新最后采集的N个数的中位数，但又不保存（至少不
: 全部保存）这N个数。请问这个问题可行么？
: 也就是想实时计算最后一段时间采集的数据的中位数，但是由于条件限制不能全部保存
: 所有数据。
: 多谢！
|
h*d
发帖数: 19309 | 10 看看这个？
http://stackoverflow.com/questions/10657503/find-running-median
教：
【在 e*****m 的大作中提到】
: 不是面试题，而是实际工作中遇到的一个问题。本人不怎么懂算法，向版上大牛们请教：
: 有一个实时采集的数列，想随时更新最后采集的N个数的中位数，但又不保存（至少不
: 全部保存）这N个数。请问这个问题可行么？
: 也就是想实时计算最后一段时间采集的数据的中位数，但是由于条件限制不能全部保存
: 所有数据。
: 多谢！
|
f*******w
发帖数: 1243 | 11 用两个heap那个也没法解决内存限制的问题啊。本质上还是存了所有的数据，只是保证
了O(1)的复杂度。 |
