subject ：

How to get the median in a data stream ？ If you read an odd number of values from the data stream , So the median is the number in the middle after all the numbers are sorted . If even numbers are read from the data stream , Then the median is the average of the middle two numbers after all the numbers are sorted . We use Insert() Method to read the data stream , Use GetMedian() Method to get the median of the currently read data .

answer ：

Solution 1 ：

Sort directly first , The code is as follows ：

import java.util.*;
public class Solution {
    ArrayList<Integer> list = new ArrayList<>();

    public void Insert(Integer num) {
        list.add(num);
    }

    public Double GetMedian() {
        Collections.sort(list);
        int size = list.size();
        if(size==0){
            return 0.00;
        }
        if(size==1){
            return (double)list.get(0);
        }
        if(size%2!=0){
            return (double)list.get(size/2);
        }else{
            return ((double)(list.get(size/2)+(double)list.get(size/2-1))/2.00);
        }
    }


}

Solution 2 ：

The largest heap and the smallest heap , Ideas as follows (leetcode On someone else's picture , See the link below for the source )：

The code is as follows ：

import java.util.*;
public class Solution {
    PriorityQueue<Integer> maxheap = new PriorityQueue<>((a,b)->b-a);
    PriorityQueue<Integer> minheap = new PriorityQueue<>();
    int count = 0;

    public void Insert(Integer num) {
        if(count%2==0){
            minheap.add(num);
            maxheap.add(minheap.poll());
        }else{
            maxheap.add(num);
            minheap.add(maxheap.poll());
        }
        count++;
    }

    public Double GetMedian() {
        if(count%2==0){
            // If it's even , Returns the average value of the top elements of the small top heap and the large top heap 
            return (double)(minheap.peek()+maxheap.peek())/2;
        }else{
            // If it's odd , Returns the top element of the big top heap 
            return (double)maxheap.peek();
        }
    }


}

Reference link ：

leetcode Answer key

The finger of the sword offer Answer key