我最近在一次面试中进行了一次编码测试.我被告知:
有一个
int万个未排序的大array.用户希望检索K个最大的元素.您将实现什么算法？
在这期间，有人强烈暗示我需要对数组进行排序.
所以，我建议使用内置sort()，或者如果性能真的很重要，可以使用自定义实现.然后我被告知，使用Collection或array来存储k个最大的for循环，可能会达到大约O(N)个，事后来看，我认为是O(N*k)个，因为每次迭代都需要与K大小的数组进行比较，以找到要替换的最小元素，而对数组进行排序的需要会导致代码至少为O(N log N).
然后我回顾了这个链接，建议优先队列为K个数字，每次发现较大的元素时，删除最小的数字，也就是O(N log N)个.Write a program to find 100 largest numbers out of an array of 1 billion numbers
for循环方法坏吗？我应该如何证明使用for循环或priorityqueue/排序方法的优缺点？我认为，如果已经对数组进行了排序，则不需要再次遍历整个数组，也就是说，如果对排序后的数组调用了其他检索方法，则应该是常数时间.在运行实际代码时，是否有一些性能因素是我在建立伪代码理论时没有考虑的？