首页 > 代码库 > 在线求中位数
在线求中位数
在线求第k个数做得多了,在线求中位数也是用堆,一个最大堆,一个最小堆。
思想大概是这样子的:
- 一个最大堆,一个最小堆,最大堆对应于前n/(n+1)个数,最小堆对应于后n/n+1个数;假设最大堆堆项元素为n1, 最小堆堆顶为n2, 则n1 <= n2;
- 确保两个堆的大小最多只差1. 设最大堆大小为s1, 最小堆大小为s2,则abs(s1-s2) <= 1;
- 对于新来的数m,分情况调整:
- 如果s1== s2, 那么:如果m<= n2, m插入到最大堆,s1= s1+1; 否则插入到最小堆,s2=s2+1;
- 如果s1 > s2, 那么:如果m >= n1, m插入到最小堆,s2=s2+1;否则,n1pop出最大堆,然后push进最小堆,然后m进最大堆,s2=s2+1;
- 如果s1 < s2, 那么:如果m <=n2, m插入到最大堆,s1=s1+1;否则,n2pop出最小堆,然后push进最大堆,然后m进最小堆,s1=s1+1;
代码如下:
在线求中位数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。