【上海校区】利用堆解决流数据的中位数问题

python 未结 0 134
seo网站排名优化软件
悬赏:83
题目描述
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

分析
利用一个大顶堆和小顶堆来解决问题。当输入数据的总量为奇数时,数据先放入小顶堆,再从小顶堆拿出堆顶元素放入大顶堆中;当为偶数时,数据先放入大顶堆,再从大顶堆中拿出堆顶元素放入小顶堆中。保证小顶堆的最小值比大顶堆的最大值要大。输出数据时,当总量为奇数时,直接输出小顶堆的堆顶元素,当为偶数时,输出大顶堆和小顶堆的堆顶元素的平均值。



代码
import java.util.Comparator;
import java.util.PriorityQueue;

public class StreamMedian {

        private int count = 0;
        private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(15,new Comparator<Integer>(){

                @Override
                public int compare(Integer arg0, Integer arg1) {
                        // TODO Auto-generated method stub
                        return arg1-arg0;
                }
               
        });
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                StreamMedian test = new StreamMedian();
                test.Insert(1);
                test.Insert(1);
                test.Insert(2);
                test.Insert(2);
                System.out.println(test.GetMedian());
        }
       
        public void Insert(Integer num){
                if(count%2 == 0){
                        maxHeap.offer(num);
                        int filteredMaxMum = maxHeap.poll();
                        minHeap.offer(filteredMaxMum);
                }else{
                        minHeap.offer(num);
                        int filteredMinNum = minHeap.poll();
                        maxHeap.offer(filteredMinNum);
                }
                count++;
        }
       
        public Double GetMedian(){
                if(count%2 == 0){
                        return (minHeap.peek() + maxHeap.peek())/2.0;
                }else{
                        return minHeap.peek()/1.0;
                }
        }
}

---------------------
作者:另一个我竟然存在
来源:CSDN
原文:https://blog.csdn.net/qq_24034545/article/details/83625357
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复