扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 场景题 > 海量数据高频面试题 > 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为小根堆,并人为固定 lr之前存在如下的大小关系:

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

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

如果r 为空,说明当前插入的是首个元素,直接添加到 l即可; 如果r不为空,且 num <= r.peek(),说明num 的插入位置不会在后半部分(不会在r中),直接加到l即可; 如果 r 不为空,且 num > r.peek(),说明 num的插入位置在后半部分,此时将r 的堆顶元素放到 l 中,再把 num放到 r(相当于从r中置换一位出来放到l中)。 插入前两者大小不同,说明前数据流元素个数为奇数,插入后变为偶数。我们期望操作完达到「lr数量相等,同时双堆维持有序」,进一步分情况讨论(此时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亿个数还是不能一次读取进内存要怎么办?

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


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