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

Question

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

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

Answer 1

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

一种方法可能是这样的：

• 对于前 10^5 个整数，将它们插入到数组中
• 对数组进行排序
• 对于剩余的整数：如果该整数大于数组的最小整数，则丢弃最小的整数并将新整数插入到数组中已排序的位置。否则，丢弃该整数。请注意，数组的大小将保持为 10^5
• 处理完所有 10^10 个整数后，结果是结果数组中最小的整数