我想到的是
那会给我O(NlogK)。有没有更好的算法？我无法进行快速选择，因为该数组无法存储在内存中。
最佳答案
根据您的内存限制，您可以使用中位数中值算法的修改版本来解决O(n)时间和O(k)空间中的问题。
这个想法如下。在内存中维护大小为2k的数组。用数组中的前2k个元素填充此缓冲区，然后对其运行中位数算法，以将最大的k个元素放置在数组的前半部分中，将最小的k个元素放置在后半部分中。然后，丢弃最小的k个元素。现在，将接下来的k个元素加载到数组的后半部分，使用中位数算法再次将顶部k个元素放置在左侧，将底部k个元素放置在右侧。如果您在整个数组上迭代此过程-用数组中的后k个元素替换缓冲区的后半部分，然后使用中位数中值将其中的前k个移到左半部分-那么最后，您将在数组的左半部分具有前k个元素。找到最小的那些(在O(k)时间内)将为您提供第k个最大的元素。
总体而言，您最终以大小为O(k)的数组对中位数算法进行O(n/k)调用，即对需要O(k)时间的算法进行O(n/k)调用，用于O(n)的净运行时间。这与最后一步结合在一起，以O(n + k)= O(n)的时间运行。此外，由于中位数步骤的内存使用量为O(k)，并且由于您有一个大小为O(k)的缓冲区，因此仅使用O(k)内存。换句话说，它的渐近速度比最小堆解快，并且在内存中渐近等效。
希望这可以帮助!
关于arrays - 在不存储整个数组的情况下单次查找第K个最大数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6446816/