memory-management - 在一组数字生成时找到它们中的第 N 个最大值

Question

我正在编写一个程序，需要在一组数字中找到第 N 个最大值。这些数字是由程序生成的，但我没有足够的内存来存储 N 个数字。是否有比 N 更好的存储上限？数字组(以及 N)的大小上限约为 100,000,000。

注意:数字是小数，列表可以包含重复项。

[编辑]:我的内存限制是 16 MB。

Answer 1

你能从一开始就重新生成同一组数字吗？如果是，您可以对输出进行多次传递:首先找到最大值，重新启动生成器，找到小于该值的最大数，重新启动生成器，然后重复此操作直到得到结果。

这将是一个真正的性能杀手，因为你有很多数字并且需要很多遍——但是在内存方面，你只需要存储 2 个元素(当前的最大值和一个“限制”，数字你在上次传球时发现的)和传球计数器。

您可以通过使用优先级队列来查找最大的 M 个元素(选择一些您能够放入内存的 M)来加快速度，从而减少 N/M 所需的传递次数。

例如，如果您需要查找 15 个数字列表中第 10 大的元素，则可以通过相反的方法来节省时间。由于它是第 10 大元素，这意味着有 15-10=5 个元素小于该元素 - 因此您可以查找第 6 小元素。