从大型未排序数组中检索K个最大元素的最佳方法？

Question

我最近在一次面试中进行了一次编码测试。我被告知：

有一个100万int的大型未排序数组。用户想要检索K个最大的元素。您将实现什么算法？

在这期间，有人强烈暗示我需要对数组进行排序。

所以，如果性能真的很重要，我建议使用内置的ort（）或自定义实现。然后我被告知，使用Collection或数组来存储k最大和for循环，可以实现大约O（N），事后看来，我认为这是O（N*k），因为每次迭代都需要与K大小的数组进行比较以找到要替换的最小元素，而对数组进行排序的需要将导致代码至少为O（N log N）。

然后我查看了SO上的这个链接，它建议K数字的优先级队列，每次找到较大的元素时都会删除最小的数字，这也会给出O（N log N）。编写一个程序，从10亿数组中找出100个最大的数字

for循环方法不好吗？我应该如何证明使用for循环或优先队列/排序方法的优缺点？我在想，如果数组已经排序，它可以通过不需要再次遍历整个数组来帮助，即如果在排序的数组上调用其他一些检索方法，它应该是恒定的时间。在运行实际代码时是否有一些我在理论化伪代码时没有考虑的性能因素？

Answer 1

这里有一个想法。我将考虑使用最大大小（2147483647）创建数组（int），因为它是int的最大值（2147483647）。然后，对于我从原始数组中得到的每个数字，只需在我创建的空数组中放入相同的索引（与数字）1。

所以在最后，对于每个，我将有类似[1,000,2,0,3]（我创建的数组）的东西，它们代表数字[0, 2, 2, 4, 4, 4]（初始数组）。

因此，要找到K最大的元素，您可以在创建的数组上为向后创建，并从K倒数到0每次当你有不同的元素时，然后是0。如果您有例如2，则必须将此数字计数2次。

这种方法的局限性在于，由于数组的性质，它仅适用于整数。。。

此外，int在java中的表示形式为-2147483648到2147483647，这意味着在需要创建的数组中只能放置正数。

注意：如果您知道int的最大值，则可以使用该最大值减小创建的数组大小。例如，如果最大int为1000，那么您需要创建的数组的大小为1000，那么该算法应该执行得非常快。

Answer 2

我认为你误解了你需要整理的东西。

您需要对K大小的列表进行排序，而不需要对原始的N大小的输入数组进行排序。这样，时间复杂度将为O（N*log（K））。

要求指出，N非常大，但K小得多，因此O（N*log（K））也比O（N*log（K））小。

对于K大小的列表，您可以看看是否有具有固定容量和自定义比较器的PriorityQueue实现，它使用PriorityQueue和一些附加逻辑。

Answer 3

解决这个问题的另一种方法是使用Quickselect。这应该会给你一个O（n）的总平均时间复杂度。考虑一下：

1. 使用Quickselect（O（n））查找第k个最大数x

（如果有重复的元素，可以通过计算需要添加到结果中的x的重复数来避免这些元素。）

您的问题与您链接到的SO问题中的问题之间的区别在于您只有一百万个元素，因此它们绝对可以保存在内存中以允许正常使用Quickselect。