连续算中位数太难了

DDD888

一个序列4,3, 8, 7, 6中位数是6，然后又有一个新的数字9，算中位数仍旧是6， 再有个新的数字10，那中位数是7，重复这过程，在计算中我不想保存所有的数字4,3, 8, 7, 6,想节约内存，还要快,如何有效计算啊？

hanxuema

你弄一个排序数组然后找中间那个index是不是就行了？

DoubleU

初始序列取中位数后你只需要保存中位数以及其左右相邻的两个数应该就可以了

chainray

什么语言？

chainray

phyton的话就是不停迭代statistics.median(data)

MerryX

新增6个以内可以只保留几个数（分新增的是不是1、2的情况）。新增超过6个数后，每多2个数（不是1、2的情况下）去掉之前保留顺序数列的1个数，中位数往后移1位。

fiony

MerryX 发表于 2021-3-4 10:18
新增6个以内可以只保留几个数（分新增的是不是1、2的情况）。新增超过6个数后，每多2个数（不是1、2的情况 ...

新增N个数，也可以按照新增一个数的方法算N遍。所以基本上就是保存3个数就好了吧

fiony

DoubleU 发表于 2021-3-4 09:34
初始序列取中位数后你只需要保存中位数以及其左右相邻的两个数应该就可以了 ...

我觉得这个是正解

DDD888

chainray 发表于 2021-3-4 09:52
什么语言？

csharp

MerryX

fiony 发表于 2021-3-4 10:22
新增N个数，也可以按照新增一个数的方法算N遍。所以基本上就是保存3个数就好了吧 ...

在新增的数字不是1、2的情况下，只有新增数目小于5（总序列数小于10）时候才能保留3个数（6、7、8）。

DDD888

DoubleU 发表于 2021-3-4 09:34
初始序列取中位数后你只需要保存中位数以及其左右相邻的两个数应该就可以了 ...

谢谢

MerryX

fiony 发表于 2021-3-4 10:23
我觉得这个是正解

如果只保留中位数左右两个，后面数越来越多的时候，每多2数，中位数就得往后移1位。后面的数不保留，那没法继续。

MerryX

DDD888 发表于 2021-3-4 10:29
谢谢

如果只保留中位数左右两个，后面数越来越多的时候，每多2数，中位数就得往后移1位。后面的数不保留，那没法继续。

MerryX

不是说中位数紧挨着新增的数，而是中间隔了很多，后面都得挨个用到。

sydgcc

你是不是在写做市商程序

yzh1999

中位数是一个空间O(n)问题吧

MerryX

我回复的也是因为楼主说8以后每次增加的是9、10这样增加（减）的，我前面说的考虑1、2是多余的。要是后面增加的数字比之前那些数字有大有小，那就没法去掉，只能全部保留。如果是有规律的递增（减），比如9，10，11，12，又是另一种算法。

DDD888

sydgcc 发表于 2021-3-4 10:40
你是不是在写做市商程序

啥是市商程序？不懂

DoubleU

MerryX 发表于 2021-3-4 10:30
如果只保留中位数左右两个，后面数越来越多的时候，每多2数，中位数就得往后移1位。后面的数不保留，那没 ...

你是对的，我欠考虑了。

楼主，如果输入都是整数而且你有内存方面的限制，试试用bit array，用数组的位置对应一个整数，比如数组是3、4、6、8，那么数组里对应的bitArray[2]=1, bitArray[3]=1，bitArray[5]=1, bitArray[7]=1, etc. 新增数字就是遍历数组并把相对应的位置设为1。

DDD888

内存有限，我想我应该放低我的要求，我打算将那序列的长度设置为10

rabbitpoint

似乎很简单的问题，结果发展到都看不懂了。

DDD888

DoubleU 发表于 2021-3-4 11:13
你是对的，我欠考虑了。

楼主，如果输入都是整数而且你有内存方面的限制，试试用bit array，用数组的位 ...

不是整数，是浮点数double

muyir

必须要保存所有的数字，
设想极端情况一，从某个时间点起，后面出现的数字都比已出现的数字大
极端情况二，从某个时间点起，后面出现的数字都比已出现的数字小

liangyu42087

这道题LEETCODE 295...

你必须要存数组啊。。。。你不存数组你怎么知道那个是中位数？？而且你也不知道后续会有加多少数字

tyler_kwok

只需要保存当前中位数，中位数前两位和后两位，以及此时中位数左边和右面的数目个数。
这样，就算数组增长到99999999+， 你还是只需要保存上诉所说的7个数，而不需要保存所有999999999+个数。

dabaobiao

tyler_kwok 发表于 2021-3-4 13:58
只需要保存当前中位数，中位数前两位和后两位，以及此时中位数左边和右面的数目个数。
这样，就算数组增长 ...

必须全部保存


举个栗子，原数列 1，2，3，4，5，6，7，8，9，中位是5
新数列增加了10，11，12，13，14，15，16，17，整个数列（1到17）中位是9
如果不保存初始数列的全部数字，不可能知道9的存在

liangyu42087

tyler_kwok 发表于 2021-3-4 13:58
只需要保存当前中位数，中位数前两位和后两位，以及此时中位数左边和右面的数目个数。
这样，就算数组增长 ...

你这样不成。

举个例子

你先开的数组是
【1，2，3，4，5，6，7，8，9，10，11】

按你的说法只保留中位和前后2位
【4，5，6，7，8】

你后面没法做啊。。。。

比如我再加上【12，13，14，15，16，17，18，19，20，21】

现在中位数是11。。。。但是你上面没存怎么办？

liangyu42087

peacefulme 发表于 2021-3-4 14:00
用两个堆，一个升序，一个降序，复杂度log（N）

正解！

MerryX

liangyu42087 发表于 2021-3-4 14:29
你这样不成。

举个例子

其实这种规律的加法，每次增加大（小）1或者多少的数，那就不用保留了，直接每增加2数中位数加每次多加（减）的数就行，这样更节省内存。无规律添加的话确实全部需要保留，除非每次添加的都比之前的全都大或者小。

liangyu42087

MerryX 发表于 2021-3-4 14:39
其实这种规律的加法，每次增加大（小）1或者多少的数，那就不用保留了，直接每增加2数中位数加每次多加（ ...

我只是举例子，为了方便所以每次只加1...