新足迹 › 论坛 › 澳洲生活区 › 工作学习 › 连续算中位数太难了

精华好帖回顾
· 我谈澳洲从军（新加面试情况） (2009-1-9) pal2002	· Build Albany 40 with Carlisle in Mernda Villages ---------开始整home theatre. (2011-5-5) 邪恶的瘦子
· 群星荟萃--TVB大制作《赌场风云》 (2008-1-2) 月亮	· 感受悉尼恶劣的交通（火车） (2005-7-27) xiangjia

12 / 2 页下一页

查看: 6492|回复: 53

[IT] 连续算中位数太难了 [复制链接]

DDD888

银靴族

发表于 2021-3-4 08:50 |显示全部楼层

此文章由 DDD888 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 DDD888 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

hanxuema

木屐族

发表于 2021-3-4 09:28 |显示全部楼层

此文章由 hanxuema 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 hanxuema 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

DoubleU

皮靴族

发表于 2021-3-4 09:34 |显示全部楼层

此文章由 DoubleU 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 DoubleU 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

chainray

白金靴族

发表于 2021-3-4 09:52 |显示全部楼层

此文章由 chainray 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 chainray 所有！转贴必须注明作者、出处和本声明，并保持内容完整

什么语言？

chainray

白金靴族

发表于 2021-3-4 09:56 |显示全部楼层

此文章由 chainray 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 chainray 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

MerryX

皮靴族

发表于 2021-3-4 10:18 来自手机 |显示全部楼层

此文章由 MerryX 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 MerryX 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

fiony

铜靴族

发表于 2021-3-4 10:22 来自手机 |显示全部楼层

此文章由 fiony 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 fiony 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

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

fiony

铜靴族

发表于 2021-3-4 10:23 来自手机 |显示全部楼层

此文章由 fiony 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 fiony 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

我觉得这个是正解

DDD888

银靴族

发表于 2021-3-4 10:26 |显示全部楼层

此文章由 DDD888 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 DDD888 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

csharp

MerryX

皮靴族

发表于 2021-3-4 10:27 来自手机 |显示全部楼层

此文章由 MerryX 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 MerryX 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

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

DDD888

银靴族

发表于 2021-3-4 10:29 |显示全部楼层

此文章由 DDD888 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 DDD888 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

谢谢

MerryX

皮靴族

发表于 2021-3-4 10:29 来自手机 |显示全部楼层

此文章由 MerryX 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 MerryX 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

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

MerryX

皮靴族

发表于 2021-3-4 10:30 来自手机 |显示全部楼层

此文章由 MerryX 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 MerryX 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

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

评分

参与人数 1	积分 +2	收起理由
fiony	+ 2	偶对你的景仰如滔滔江水

查看全部评分

MerryX

皮靴族

发表于 2021-3-4 10:32 来自手机 |显示全部楼层

此文章由 MerryX 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 MerryX 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

sydgcc

皮靴族

发表于 2021-3-4 10:40 |显示全部楼层

此文章由 sydgcc 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 sydgcc 所有！转贴必须注明作者、出处和本声明，并保持内容完整

你是不是在写做市商程序

yzh1999

银靴族

发表于 2021-3-4 10:52 来自手机 |显示全部楼层

此文章由 yzh1999 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 yzh1999 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

MerryX

皮靴族

发表于 2021-3-4 11:01 来自手机 |显示全部楼层

此文章由 MerryX 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 MerryX 所有！转贴必须注明作者、出处和本声明，并保持内容完整

本帖最后由 MerryX 于 2021-3-4 14:35 编辑

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

DDD888

银靴族

发表于 2021-3-4 11:12 |显示全部楼层

此文章由 DDD888 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 DDD888 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

啥是市商程序？不懂

DoubleU

皮靴族

发表于 2021-3-4 11:13 |显示全部楼层

此文章由 DoubleU 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 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

银靴族

发表于 2021-3-4 11:14 |显示全部楼层

此文章由 DDD888 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 DDD888 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

rabbitpoint

白金靴族

发表于 2021-3-4 11:24 |显示全部楼层

此文章由 rabbitpoint 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 rabbitpoint 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

DDD888

银靴族

发表于 2021-3-4 11:26 |显示全部楼层

此文章由 DDD888 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 DDD888 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

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

不是整数，是浮点数double

muyir

布鞋族

发表于 2021-3-4 13:40 |显示全部楼层

此文章由 muyir 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 muyir 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

liangyu42087

铜靴族

发表于 2021-3-4 13:56 |显示全部楼层

此文章由 liangyu42087 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 liangyu42087 所有！转贴必须注明作者、出处和本声明，并保持内容完整

这道题LEETCODE 295...

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

tyler_kwok

头像被屏蔽

禁止发言

发表于 2021-3-4 13:58 |显示全部楼层

此文章由 tyler_kwok 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 tyler_kwok 所有！转贴必须注明作者、出处和本声明，并保持内容完整

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

签名被屏蔽

dabaobiao

铜靴族

发表于 2021-3-4 14:25 |显示全部楼层

此文章由 dabaobiao 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 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

铜靴族

发表于 2021-3-4 14:29 |显示全部楼层

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。。。。但是你上面没存怎么办？