9. 5亿个int找它们的中位数

中位数是按顺序排列的一组数据中居于中间位置的数，如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。

如果题目没有内存限制，只需将5亿个数直接读取到内存中，然后排序，找到中间的数即可

方法一

但排序的时间复杂度最快也得O(NlogN)，想用空间换时间有没有什么好办法呢？

当然是有的，请看力扣295题（数据流的中位数），https://leetcode-cn.com/problems/find-median-from-data-stream/

为了方便，这里贴出了一个高赞题解，原链接：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/gong-shui-san-xie-jing-dian-shu-ju-jie-g-pqy8/

我们可以使用两个优先队列（堆）来维护整个数据流数据，令维护数据流左半边数据的优先队列（堆）为l，维护数据流右半边数据的优先队列（堆）为 r。

显然，为了可以在 O(1) 的复杂度内取得当前中位数，我们应当令 l 为大根堆，r为小根堆，并人为固定 l和r之前存在如下的大小关系：

当数据流元素数量为偶数：l 和r 大小相同，此时动态中位数为两者堆顶元素的平均值； 当数据流元素数量为奇数：l 比 r 多一，此时动态中位数为 l的堆顶原数。 为了满足上述说的奇偶性堆大小关系，在进行 addNum 时，我们应当分情况处理：

插入前两者大小相同，说明插入前数据流元素个数为偶数，插入后变为奇数。我们期望操作完达到「l的数量为r多一，同时双堆维持有序」，进一步分情况讨论：

如果r 为空，说明当前插入的是首个元素，直接添加到 l即可； 如果r不为空，且 num <= r.peek()，说明num 的插入位置不会在后半部分（不会在r中），直接加到l即可； 如果 r 不为空，且 num > r.peek()，说明 num的插入位置在后半部分，此时将r 的堆顶元素放到 l 中，再把 num放到 r（相当于从r中置换一位出来放到l中）。 插入前两者大小不同，说明前数据流元素个数为奇数，插入后变为偶数。我们期望操作完达到「l和r数量相等，同时双堆维持有序」，进一步分情况讨论（此时l必然比r 元素多一）：

如果 num >= l.peek()，说明num的插入位置不会在前半部分（不会在 l中），直接添加到 r 即可。 如果 num < l.peek()，说明 num 的插入位置在前半部分，此时将 l 的堆顶元素放到r 中，再把 num 放入 l中（相等于从l 中替换一位出来当到r 中）。

Java代码

class MedianFinder {
    PriorityQueue<Integer> l = new PriorityQueue<>((a,b)->b-a);
    PriorityQueue<Integer> r = new PriorityQueue<>((a,b)->a-b);
    
    public void addNum(int num) {
        int s1 = l.size(), s2 = r.size();
        if (s1 == s2) {
            if (r.isEmpty() || num <= r.peek()) {
                l.add(num);
            } else {
                l.add(r.poll());
                r.add(num);
            }
        } else {
            if (l.peek() <= num) {
                r.add(num);
            } else {
                r.add(l.poll());
                l.add(num);
            }
        }
    }
    
    public double findMedian() {
        int s1 = l.size(), s2 = r.size();
        if (s1 == s2) {
            return (l.peek() + r.peek()) / 2.0;
        } else {
            return l.peek();
        }
    }
}

时间复杂度：addNum 函数的复杂度为O(logn)；findMedian函数的复杂度为O(1)

空间复杂度：O(n)

方法二

当然如果内存不足怎么办，不能把数据全部放入内存

还是之前的老办法，分治法。但是这道题不能用hash映射的方法分流，因为这是无序的，而把数据打乱分散到不同文件中就找不到中位数了，所以需要一种按大小分流的方法。

首先遍历这5亿个数，遍历的时候将每个数转换位二进制，如果最高位为1存入文件1，最高位为0存入文件2，这样文件1中的数是一定比文件2中的小的。因为最高位是符号位，0表示正数，1表示负数

如果恰好文件1和文件2中的数都是2.5亿个，那么中位数则是文件1中的最小值和文件2中的最大值的平均值。

一般不会这么恰好，假设文件1中的数为2亿个，文件2中的数为3亿个，那么中位数是文件中的第五千万个数及下一个数的平均值。

那3亿个数还是不能一次读取进内存要怎么办？

还是使用这个方法根据次高位进行分流，并一直关注位数的位置，直到中位数所在的那部分数据大小可以直接放到内存中，然后对这部分排序，计算出中位数的值

本站链接：https://www.mianshi.online，如需勘误或投稿，请联系微信：lurenzhang888

点击面试手册，获取本站面试手册PDF完整版