[剑指offer-JZ63]数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 **解法一：**利用优先队列（堆）保存数据流中的数,时间复杂度O(logn)

import java.util.PriorityQueue; import java.util.Comparator; public class Solution { int count=0; //创建优先队列，默认小顶堆，存放数据流中的大数据 PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>(); PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(new Comparator<Integer>(){ public int compare(Integer o1, Integer o2) { return o2 - o1; } }); public void Insert(Integer num) { //当count为偶数时，往大顶堆中加入元素，同时将大顶堆中的最大值取出放入小顶堆，保证小顶堆的数始终大于大顶堆 if(count%2==0){ maxHeap.offer(num); //poll：将首个元素从队列中弹出，如果队列是空的，就返回null int max=maxHeap.poll(); minHeap.offer(max); }else { //当count为奇数时，往小顶堆中加入元素，同时将小顶堆中的最小值取出放入大顶堆 minHeap.offer(num); int min=minHeap.poll(); maxHeap.offer(min); } count++; } public Double GetMedian() { if(count%2==0){ return (minHeap.peek()+maxHeap.peek())/2.0; //peek：查看首个元素，不会移除首个元素，如果队列是空的就返回null } else { return (new Double(minHeap.peek())); } } }

解法二：利用list存储插入的数据，边插入边进行排序。时间O(n)

import java.util.ArrayList; public class Solution { ArrayList<Integer> list=new ArrayList<Integer>(); public void Insert(Integer num) { if(list.size()==0) list.add(num); else{ int i=0; for(;i<list.size();i++){ if(list.get(i)>num){//加入的过程中进行排序，升序 break; } } list.add(i,num);//把num放在下标为i的位置 } } public Double GetMedian(){ int len=list.size(); if(len%2==0) return (list.get(len/2)+list.get(len/2-1))/2.0; else return (list.get(len/2))/1.0; } }