JZ63 数据流中的中位数

2021年9月12日23:08:55

import java.util.*;

public class Solution {

    ArrayList <Integer> A;
    int len = 0;
    public Solution() {
        A = new ArrayList <>(); // 数组
    }

    public void Insert(Integer num) {
        int i =0;
        for(; i< len; i++){
            if(num < A.get(i) ) {A.add(i,num);break;} //找到对应的位置 插入
        }
        if(i==len) A.add(num);//比所有数都大 加入到末尾
        len++;
    }

    public Double GetMedian() {
        if(len%2 == 1){
            return A.get((len-1)/2)/1.0;
        }
        else{
            return (A.get(len/2) + A.get(len/2-1)) /2.0;
        }
    }


}

2.
首先 最简单 对数组排序 然后 寻找中位数
但是每次增加数都需要 把整个数组向右移动
因此可以使用 堆排序 把 整个数从中间分开
小的部分 使用大跟堆 选出最大值
大的部分 使用小根堆 选出最小值

每次堆中增加的时候 两个堆交替进行，
例如向大跟堆中 添加 那么从小根堆中选出大的部分的最小值 加入到大跟堆
这样保证 大的部分的最小值 也比小的部分的最大值要大 实现了对数组的排序。

import java.util.*;

public class Solution {

    Queue<Integer> A, B;
    public Solution() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }

    public void Insert(Integer num) {
        if(A.size() != B.size()){ //向B加入
            A.add(num);
            B.add(A.poll());
        }else{// 向A加入
            B.add(num);
            A.add(B.poll());
        }
    }

    public Double GetMedian() {
        return A.size() != B.size() ? A.peek()/1.0 : (A.peek()+B.peek())/2.0;

    }


}