用多个机器寻找数据流中的中位数，如何写算法

2019/1/23镜像同步30 回复

面试时被问到找数据流中的中位数，也就是LeetCode第295题https://leetcode.com/problems/find-median-from-data-stream，我们知道这道题最常用的方法是用两个堆，但面试官要求是数据量很大，所以不得不用多个机器处理这一个数据量，请问算法怎么写，我一下子蒙圈了，所以来求教下大家该怎么写

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

intmain机器人#1 · 2019/1/24

PMS机器人#2 · 2019/1/24

【在 intmain 的大作中提到: 】 : bd 谢谢学弟

Rclover机器人#3 · 2019/1/24

每个机器存储一部分数据，查询的时候二分答案？不知道行不行

PMS机器人#4 · 2019/1/24

【在 Rclover 的大作中提到: 】 : 每个机器存储一部分数据，查询的时候二分答案？不知道行不行能再具体说说吗

a940100079机器人#5 · 2019/1/24

多个机器，每个机器存储不同区间的数字然后找到对应区间然后去区间机器用堆找中位数？

Rclover机器人#6 · 2019/1/24

我想的是比如每个机器都维护一个排序二叉树，支持插入一个数x和查询这个二叉树中小于x的数的数量。在数据流中出现一个数之后，随便把这个数插入到某一个机器的二叉树里面。查询的时候，二分地枚举答案x，查询每个机器中小于x的数的数量。但我觉得还是楼上的方法更简单一些[ema41] 【在 PMS 的大作中提到: 】 : : 能再具体说说吗

PMS机器人#7 · 2019/1/24

【在 a940100079 的大作中提到: 】 : 多个机器，每个机器存储不同区间的数字 : 然后找到对应区间 : 然后去区间机器用堆找中位数？太感谢了，我觉得你的方法最对了

PMS机器人#8 · 2019/1/24

【在 Rclover 的大作中提到: 】 : 我想的是比如每个机器都维护一个排序二叉树，支持插入一个数x和查询这个二叉树中小于x的数的数量。 : 在数据流中出现一个数之后，随便把这个数插入到某一个机器的二叉树里面。 : 查询的时候，二分地枚举答案x，查询每个机器中小于x的数的数量。 : ................... 太感谢了，确实我也觉得楼上的方法实现起来更简单些

Nroskill机器人#9 · 2019/1/24

这个方法实现简单但是感觉负载均衡做起来很难【在 a940100079 的大作中提到: 】 : 多个机器，每个机器存储不同区间的数字 : 然后找到对应区间 : 然后去区间机器用堆找中位数？