连续算中位数太难了

liangyu42087

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

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

taku

如果允许重复增加相同的数字的话，只保留两个是不行的。

linzh

如果数组不连续无规律, 只保留左右是肯定不行的, 任意移一步就不知道下一个该是谁了,
相应的, 保留N个也只是说明你能够承受移动多少下而已, 一出边界你就瞎了,
去纠结保留多少不如思考一下存储结构, 比如, 如果数组内有大量连续片段, 我们可以考虑把每个连续段计成一个子数组, 或者去记空位,

我记得以前第一次见中位数问题好像是教材里用二叉树来存放数组, ?,

woshizhuang110

我觉得是要保存所有的数的，最优的时间复杂度是O(logN)，空间是O(N)。Leetcode有原题

每次控制2个堆，左边的是最大堆，右边是最小堆。

2个堆的长度差<=1。 这样只要维护好2个堆，每次要算中位数的时候，哪个堆多1个，多的那个的堆顶的值就是中位数，如果2个堆相等那就左右各取堆顶1个除以2.

比如楼主例子 刚开始的 4，3，8，7，6

那么原始的堆是  heap_left[3,4,6] ,heap_right[7, 8]   
这时候左边比右边多1，所以左边堆顶值是 6，也就是中位数

后面来个 9 继续维护这个堆 heap_left[3,4,6], heap_right[7,8,9]  
此时两边长度一样，所以左边最大堆出 6 右边最小堆出7，中位数是 (6+7)/2

如果在来个10， 10 比左边最大堆的值还大，所以放到右边 heap_left[3,4,6], heap_right[7,8,9,10]
此时右边多1，所以中位数是 右边堆顶 7

如果在来个数比如11， 比左边最大值还大，那也要放到右边，但是由于右边长度此时已经比左边多1了，所以要把右边的堆顶也就是7放到左边，为的就是保证左右长度不超过1,此时的堆是 heap_left[3,4,6,7], heap_right[8,9,10,11], 两边长度相等，中位数是 (7+8)/2


只要维护好2个堆，长度差<=1，最快O(logN)能算出中位数，数字越多越快相比O(N)
                 

MerryX

linzh 发表于 2021-3-4 15:00
如果数组不连续无规律, 只保留左右是肯定不行的, 任意移一步就不知道下一个该是谁了,
相应的, 保留N个也只 ...

貌似通过二叉树能找到中位数。

tyler_kwok

试试演算一下，只保存目前中位数，和中位数两边的数字个数：

目前数组[0，1，2，3，99，100，200，300]，假设如果数组数目是偶数n的话，取第n/2位为中位数，比如目前有8位，则第8/2即第4位数字3为中位数。3的左边有3个数，右边有4个数。

1st迭代，加入数字7，原始数组变成[0，1，2，3，7，99，100，200，300]，此时3的左边有3+0个数，右边有4+1个数，左右相差超过1，应取（3，7）中较大的7为中位数。此时中位数7左边有4个数，右边有4个数。

2nd迭代，加入数字9，原始数组变成[0，1，2，3，7，9，99，100，200，300]，此时7的左边有4+0个数，右边有4+1个数，应取7为中位数，此时中位数7左边有4个数，右边有5个数。

3rd迭代，加入数字5，原始数组变成[0，1，2，3，5，7，9，99，100，200，300]，此时7的左边有4+1个数，右边有5+0个数，应取7为中位数，此时中位数7左边有5个数，右边有5个数。

...

我觉得这个算法应该可以，有空写段代码确认一下。

yzh1999

woshizhuang110 发表于 2021-3-4 15:05
我觉得是要保存所有的数的，最优的复杂度是O(logN)。Leetcode有原题

每次控制2个堆，左边的是最大堆，右边 ...

logN是时间还是空间复杂度

MerryX

tyler_kwok 发表于 2021-3-4 15:22
试试演算一下，只保存目前中位数，和中位数两边的数字个数：

目前数组[0，1，2，3，99，100，200，300]， ...

这种排序方法看着很眼熟，但是忘了叫什么名，貌似和冒泡递归等一起学过，不过貌似不解决这个问题。

woshizhuang110

yzh1999 发表于 2021-3-4 15:27
logN是时间还是空间复杂度

时间是O(logN)，空间是O(N)

AuMech

c# 直接用SortedList 好了

MerryX

LeetCode上的，仅供参考
https://leetcode-cn.com/problems ... de-zhong-wei-s-114/

DDD888

AuMech 发表于 2021-3-4 15:51
c# 直接用SortedList 好了

我设置了数组的长度例如10，先进先出，用了Queue<double>和SortedList<double, bool>

frank_au

问题定义不清晰，无解

liangyu42087

AuMech 发表于 2021-3-4 15:51
c# 直接用SortedList 好了

时间复杂度超标。

1. add to list 是 1
2. sort是 N log n
3. list 查找是N

时间提升到每加一个都是nlogn

DDD888

liangyu42087 发表于 2021-3-5 08:59
时间复杂度超标。

1. add to list 是 1

3. list 查找是N

不是啦，是1啦
代码是sortedList.Keys[sortedList.Count / 2];

DDD888

frank_au 发表于 2021-3-5 08:14
问题定义不清晰，无解

这许多人积极讨论，显然大家都理解了问题，何来问题定义不清晰？

liangyu42087

DDD888 发表于 2021-3-5 09:03
3. list 查找是N

不是啦，是1啦

Array 查找是1
List 查找是N


不过我没用过c#，不知道底层是怎样实现的。

DDD888

liangyu42087 发表于 2021-3-5 09:26
Array 查找是1
List 查找是N

中间数不需要查找的呀，对半开就行啦

AuMech

liangyu42087 发表于 2021-3-5 08:59
时间复杂度超标。

1. add to list 是 1

c# 可以直接用下标访问list里的元素
sort的复杂度可以相信微软的优化

对半分两个SortedList，时间复杂度就下来了

唯一的问题是sortedlist不允许duplicated key

liangyu42087

DDD888 发表于 2021-3-5 11:49
中间数不需要查找的呀，对半开就行啦

假如是LIST的话，底层实现应该是这样的。

L1 -> L2 -> L3 -> L4 ....... -> Ln

所以假如你要找L10 就只能从L1一个一个从头开始往后走。。。。就算上层语言有类似这种 list[n / 2]只要底层实现是LIST他的查找就是N.

有兴趣的话可以看一下LinkedLIst vs ArrayList的不同。  
https://www.baeldung.com/java-collections-complexity

当然，我对C#不熟悉具体底层怎么实现的不清楚。

liangyu42087

AuMech 发表于 2021-3-5 12:01
c# 可以直接用下标访问list里的元素
sort的复杂度可以相信微软的优化

https://medium.com/@lifei.888619 ... tedset-19a69fe184e0

看了一下C#的SORTEDLIST

底层实现是靠2 ARRAY。。。

SortedList is implemented with two internal arrays for keys and values.

这样的话 add是N, 查找是 logN

回到原题的话，还是增加了时间复杂度。

Add (N)
Find (Log N)

整体时间复杂变成N, 最优解还是2 PRIORITY QUEUE时间复杂度可以降到logN.

AuMech

liangyu42087 发表于 2021-3-5 12:54
假如是LIST的话，底层实现应该是这样的。

L1 -> L2 -> L3 -> L4 ....... -> Ln

不对啊，如果SortedList底层是两个array，那查找复杂度不是应该和keys的array一样么？

另外如果第一次sort完从中间分两个SortedList，每次加一个数就到其中一个里，如果一个list比另一个的元素数量多两个就调整一下. 中位数就是小的list最后一个或者大的第一个或者二者平均数，这样查找起来复杂度就是1了吧。难道找一个list最后一个也要从第一个往后找？

liangyu42087

AuMech 发表于 2021-3-5 13:32
不对啊，如果SortedList底层是两个array，那查找复杂度不是应该和keys的array一样么？

另外如果第一次so ...

[不对啊，如果SortedList底层是两个array，那查找复杂度不是应该和keys的array一样么?]



[另外如果第一次sort完从中间分两个SortedList，每次加一个数就到其中一个里，如果一个list比另一个的元素数量多两个就调整一下. 中位数就是小的list最后一个或者大的第一个或者二者平均数，这样查找起来复杂度就是1了吧。难道找一个list最后一个也要从第一个往后找？]

１.　C＃这个SORTEDLIST看样子查找就是根据二分查找，时间是（ＬｏｇＮ）
２.　既然是ARRAY，你往ARRAY里面添加东西就是（N)　你有可能需要RESIZE
３.　这个需要SORTED所以你往里面添加一定是（N) ，因为你要一个一个比过去

edit第三条错了，应该是这样
3. Sorted可以用二分查找找到正确的插入位置（logN)，但是随后有需要shift现有的数字是 (N) ，两者取大(N)

frank_au

学习氛围浓厚

AuMech

liangyu42087 发表于 2021-3-5 14:08
[不对啊，如果SortedList底层是两个array，那查找复杂度不是应该和keys的array一样么?]

研究深入