从整数流查找位数 [英] Find the median from a stream of integers

问题描述

由于整数流入你的程序作为一个流一个未排序的序列。

Given an unsorted sequence of integers that flows into your program as a stream.

该整数太多，以适应到内存中。

The integers are too many to fit into memory.

想象一下，有一个函数：

Imagine there is a function:

int getNext() throws NoSuchElementException;

它返回从流中的下一个整数。

It returns the next integer from the stream.

写一个函数，找到中位数。

Write a function to find the median.

解决O（n）的问题。

Solve the problem in O(n).

任何想法？

提示给出（使用堆的数据结构。）

Hint is given (use heap the data structure..)

推荐答案

请参阅本的纸。这将（可能）需要一个以上的传递。我们的想法是，在每次通过上界和下界被计算，使得中值位于它们之间。

See this paper. It will (likely) take more than one pass. The idea is that in each pass upper and lower bounds are computed such that the median lies between them.

下面的一个基本结果是 N 的=数据大小， P 的=进程数

A fundamental result here is N = size of data, P = number of passes

定理2）的 P 的-pass算法选择的 K 的^日最高的 N 的元素需要 储存最多的 O（N ^{（ 1 / <子> P ）}（日志N）^{（2 - 2 / <子> P ）}）的。

Theorem 2) A P-pass algorithm which selects the K^th highest of N elements requires storage at most O(N^(1/_P)(log N)^(2-2/_P)).

此外，对于非常小的存储空间的取值的，即对 2'= S＆LT; = O（（日志N） ² ）的，有一类材料，即使用选择算法 最多的 O（（日志N） ^{3 / S} ）的通行证。

Also, for very small amounts of storage S, i.e., for 2 <= S <= O((log N)²), there is a class of selection algorithms which use at most O((log N)^3/S) passes.

看报纸。我真的不知道什么是堆有什么关系呢

Read the paper. I'm not really sure what the heap has to do with it

这篇关于从整数流查找位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！