普拓网站建设,郑州网站制作_郑州网页制作_做网站设计_河南网站制作网,南皮县建设局网站,网站瀑布流怎么做题目 如何得到一个数据流中的中位数#xff1f;如果从数据流中读出奇数个数值#xff0c;那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值#xff0c;那么中位数就是所有数值排序之后中间两个数的平均值。 例如#xff0c;[2,3,4] 的中位数是…题目 如何得到一个数据流中的中位数如果从数据流中读出奇数个数值那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值那么中位数就是所有数值排序之后中间两个数的平均值。 例如[2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 3) / 2 2.5 设计一个支持以下两种操作的数据结构 void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() -返回目前所有元素的中位数。 思路
优先队列 / 堆 给定一长度为 N 的无序数组其中位数的计算方法首先对数组执行排序使用 O(NlogN)时间然后返回中间元素即可使用 O(1) 时间 本题可以根据上述思想将数据流保存在一个列表中并在添加元素时保持数组有序给定一长度为 N 的无序数组其中位数的计算方法首先对数组执行排序使用 O(NlogN) 时间然后返回中间元素即可使用 O(1)时间 借助 堆 进行优化时间复杂度 建立两个堆一个小顶堆A一个大顶堆B各自保存列表的一半元素 其中
A保存较大的一半长度为N/2或者N1/2B保存较小的一半长度为N/2或者N1/2
最后中位数可以仅根据A,B的堆顶元素计算得到 举个例子数据流 [12345678]
如图所示则[1234]保存在大顶堆B且堆顶元素为4因为大顶堆堆顶元素最大然后[5678]保存在小顶堆A且堆顶元素为5因为小顶堆堆顶元素最小这也是为什么大顶堆保存较小的一半小顶堆保存较大的一半为了就是可以通过A,B的堆顶元素求中位数
算法流程
设元素总数为 N m n 其中 m 和 n 分别为 A 和 B 中的元素个数
addNum(num) 函数添加元素 1当 mn即 N 为 偶数需向 A 添加一个元素即A和B中元素个数相等时优先往A中先加元素。实现方法将新元素 num插入至 B 再将 B 堆顶元素插入至 A 这是为了始终保证A中存较大的一半B中存较小的一半因为num可能属于较小的一半即B中的元素所以要先加入B再将B堆顶元素插入A
举个例子A中加入1需要先加入B中然后将B的堆顶元素3加入A
2当 m≠n即 N 为 奇数需向 B 添加一个元素此时情况即为A比B多一个元素。实现方法将新元素 num 插入至 A 再将A 堆顶元素插入至 B 同理为了始终保证A中存较大的一半B中存较小的一半要先加入A再将A的堆顶元素插入B因为num可能属于较大的一般分即属于A的元素
举个例子B中加入6需要先加入A中然后将A的堆顶元素3加入B
findMedian() 函数找中位数 1当 mn N 为 偶数则中位数为 ( A 的堆顶元素 B 的堆顶元素 ) / 2 2当 m≠n N 为 奇数则中位数为 A 的堆顶元素。
复杂度分析
时间复杂度 1查找中位数 O(1) 获取堆顶元素使用 O(1) 时间 2添加数字 O(logN) 堆的插入和弹出操作使用 O(logN)时间空间复杂度O(N)其中 N 为数据流中的元素数量小顶堆 A 和大顶堆 B 最多同时保存 N个元素。
java代码如下
class MedianFinder{QueueInteger A,B;public MedianFinder() {A new PriorityQueue();//java默认小顶堆保存较大的一半B new PriorityQueue((x,y) - (y - x));//使用降序定义大顶堆因为大顶堆堆顶元素最大所以是降序但是用于升序排序因为每次出堆顶元素是最大的保存较小的一半}public void addNum(int num){if(A.size() ! B.size()){//如果AB元素个数不相等则往B中添加元素//但是为了始终保证A中存较大的一半B中存较小的一半A.add(num);//要先往A中加B.add(A.poll());//然后再将A的堆顶元素加入B} else {//如果AB元素个数相等则往A中添加元素//同理为了始终保证A中存较大的一半B中存较小的一半B.add(num);A.add(B.poll());//要先往B中加//然后再将B的堆顶元素加入A}}public double findMedian(){return A.size() ! B.size() ? A.peek() : (A.peek() B.peek()) / 2.0;}
}
