剑指offer---63.数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解法一：借助API

思路： 估计又是找不到工作的方法

import java.util.*; public class Solution { ArrayList<Integer> list = new ArrayList<>(); public void Insert(Integer num) { list.add(num); Collections.sort(list); } public Double GetMedian() { int len = list.size(); if((len&1)==1) return (double)list.get(len>>1); double result = (double)(list.get(len/2)+list.get(len/2-1))/2; return result; } }

解法二：优化一下

import java.util.*; public class Solution { ArrayList<Integer> list = new ArrayList<>(); public void Insert(Integer num) { int len = list.size(); if(len==0) list.add(num); else{ while(len>0&&num<list.get(len-1)){ len--; } list.add(len,num); } } public Double GetMedian() { int len = list.size(); if((len&1)==1) return (double)list.get(len>>1); return (double)(list.get(len>>1)+list.get((len>>1)-1))/2; } }

解法二：利用两个堆

思路： java中PriorityQueue是用堆来实现的

import java.util.*; public class Solution { int count = 0; PriorityQueue<Integer> min = new PriorityQueue<>(); PriorityQueue<Integer> max = new PriorityQueue<>(20,new Comparator<Integer>(){ @Override public int compare(Integer o1,Integer o2){ return o2-o1; } }); public void Insert(Integer num) { if(count%2==0){ min.offer(num); int tmpmax = min.poll(); max.offer(tmpmax); }else{ max.offer(num); int tmpmin = max.poll(); min.offer(tmpmin); } count++; } public Double GetMedian() { if(count%2==0){ int tmpmax = max.peek(); int tmpmin = min.peek(); return (double)(tmpmax+tmpmin)/2; }else{ int tmpmax = max.peek(); return (double)tmpmax; } } }

解法四：平衡二叉树 下会刷再看吧。。。