如何在 10^10 个元素的数组中查找第 10^5 个最大元素？

Question

使用种子为 4020 的 PRNG（前 3 个数字为 -2123524894 961034805 1071375651）生成 10^10 个整数。打印生成的数字中第 10^5 大的元素。

当然，如果问题规模较小，我本来可以点击一下解决它，但我不知道如何解决它。 一种方法是使用堆方法（糟糕的想法）使用中位数，然后尝试将输入分成块并尝试在其中找到它，但这些方法都不起作用。我认为我陷入了错误的事情，这个问题的解决方案不可能需要超级计算机来计算，所以我的想法当然是错误的，你能帮我指出正确的方向，告诉我我能做些什么来解决这个问题？

Answer 1

请注意，10^10 比 10^5 大得多（100,000 倍），因此请避免存储所有 10^10 整数。

一种方法可能是这样的：

• 对于前 10^5 个元素，将它们插入到数组中
• 对数组进行排序
• 对于剩余元素：如果该元素大于数组中的最小元素，则丢弃最小元素并将新元素插入到数组中已排序的位置。否则，丢弃该元素
• 结果是结果数组中的最小元素