如何从 5 亿个数中找出中位数?

作者: Java面试

题目描述

从 5 亿个数中找出中位数。数据排序后,位置在最中间的数就是中位数。当样本数为奇数时,中位数为 第 (N+1)/2 个数;当样本数为偶数时,中位数为 第 N/2 个数与第 1+N/2 个数的均值。

解答思路

如果这道题没有内存大小限制,则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为 O(NlogN) 。这里使用其他方法。

方法一:双堆法

维护两个堆,一个大顶堆,一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数;保证这两个堆中的元素个数的差不超过 1。

若数据总数为偶数,当这两个堆建好之后,中位数就是这两个堆顶元素的平均值。当数据总数为奇数时,根据两个堆的大小,中位数一定在数据多的堆的堆顶

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        minHeap = new PriorityQueue<>(Integer::compareTo);
    }
    public void addNum(int num) {
        if (maxHeap.isEmpty() || maxHeap.peek() > num) {
            maxHeap.offer(num);
            minHeap.offer(num);
        }
        int size1 = maxHeap.size();
        int size2 = minHeap.size();
        if (size1 - size2 > 1) {
            minHeap.offer(maxHeap.poll());
        } else if (size2 - size1 > 1) {
            maxHeap.offer(minHeap.poll());
        }
    }
    public double findMedian() {
        int size1 = maxHeap.size();
        int size2 = minHeap.size();
        return size1 == size2
            ? (maxHeap.peek() + minHeap.peek()) * 1.0 / 2
            : (size1 > size2 ? maxHeap.peek() : minHeap.peek());
    }
}

见 LeetCode No.295:https://leetcode.com/problems/find-median-from-data-stream/

以上这种方法,需要把所有数据都加载到内存中。当数据量很大时,就不能这样了,因此,这种方法适用于数据量较小的情况。5 亿个数,每个数字占用 4B,总共需要 2G 内存。如果可用内存不足 2G,就不能使用这种方法了,下面介绍另一种方法。

方法二:分治法

分治法的思想是把一个大的问题逐渐转换为规模较小的问题来求解。

对于这道题,顺序读取这 5 亿个数字,对于读取到的数字 num,如果它对应的二进制中最高位为 1,则把这个数字写到 f1 中,否则写入 f0 中。通过这一步,可以把这 5 亿个数划分为两部分,而且 f0 中的数都大于 f1 中的数(最高位是符号位)。

划分之后,可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数,那么中位数一定在 f0 中,且是在 f0 中,从小到大排列的第 1.5 亿个数与它后面的一个数的平均值。

提示,5 亿数的中位数是第 2.5 亿与右边相邻一个数求平均值。若 f1 有一亿个数,那么中位数就是 f0 中从第 1.5 亿个数开始的两个数求得的平均值。

对于 f0 可以用次高位的二进制继续将文件一分为二,如此划分下去,直到划分后的文件可以被加载到内存中,把数据加载到内存中以后直接排序,找出中位数。

注意,当数据总数为偶数,如果划分后两个文件中的数据有相同个数,那么中位数就是数据较小的文件中的最大值与数据较大的文件中的最小值的平均值。

方法总结

分治法,真香!

更多推荐

更多
  • Docker从入门到实践-底层实现-命名空间 命名空间,pid 命名空间,net 命名空间,ipc 命名空间,mnt 命名空间,uts 命名空间,user 命名空间,保证了容器之间彼此互不影响。 pid 命名空间 --------------------------- 不同用
  • Docker从入门到实践-底层实现-基本架构 基本架构,并处理这些请求(创建、运行、分发容器)。 客户端和服务端既可以运行在一个机器上,也可通过 `socket` 或者 `RESTful API` 来进行通信。 ![Docker 基本架构](https://static.oom
  • Docker从入门到实践-底层实现-控制组 控制组,,主要用来对共享资源进行隔离、限制、审计等。只有能控制分配到容器的资源,才能避免当多个容器同时运行时的对系统资源的竞争。 控制组技术最早是由 Google 的程序员在 2006 年提出,Linux 内核自 2.6.24 开始支
  • Docker从入门到实践-底层实现-容器格式 容器格式,er](https://github.com/docker/libcontainer),从 1.11 开始,则进一步演进为使用 [runC](https://github.com/opencontainers/runc) 和
  • Docker从入门到实践-底层实现-网络 Docker 网络实现,基本原理,创建网络参数,网络配置细节,悉了解这两部分的基本概念再阅读本章。 基本原理 ----------------------- 首先,要实现网络通信,机器需要至少一个网络接口(物理接口或虚拟接口)来收
  • Docker从入门到实践-底层实现-联合文件系统 联合文件系统,并且高性能的文件系统,它支持对文件系统的修改作为一次提交来一层层的叠加,同时可以将不同目录挂载到同一个虚拟文件系统下(unite several directories into a single virtual file
  • Docker从入门到实践-底层实现 底层实现,文件系统(Union file systems)和容器格式(Container format)。 们知道,传统的虚拟机通过在宿主主机中运行 hypervisor 来模拟一整套完整的硬件环境提供给虚拟机的操作系统。虚拟机系统看
  • Docker从入门到实践-Swarm mode-部署服务 部署服务,新建服务,查看服务,服务伸缩,删除服务,AME IMAGE NODE DESIRED STATE CURRENT STATE ERROR PORTS * pjfzd39buzlt nginx.1 nginx:1.13.
  • Docker从入门到实践-Swarm mode-创建 Swarm 集群 创建 Swarm 集群,初始化集群,增加工作节点,查看集群,有了一个管理节点,下面们继续创建两个 Docker 主机作为工作节点,并加入到集群中。 ``` * $ docker-machine create -d virt
  • Docker从入门到实践-Swarm mode-管理配置信息 在 Swarm 集群中管理配置数据,创建 config,查看 config,创建 redis 服务,----- 新建 `redis.conf` 文件 ``` * port 6380 ``` 此项配置 Redis
  • 近期文章

    更多
    文章目录

      推荐作者

      更多