我正在尝试编写一种算法，可以在O(n)的时间中将n个最小的数字打印在n个大小的数组中，但是我无法将时间复杂度降低到n。我怎样才能做到这一点？
最佳答案
我之前在采访中已经做到了，最优雅/最有效的方法之一是
O(n log k).
with space: O(k) (thanks, @Nzbuu)
基本上，您将使用大小限制为k的最大堆。对于数组中的每个项目，请检查其是否小于最大值(仅O(1))。如果是，请删除最大值并将其放入堆(O(log k))。如果更大，请转到下一个项目。
当然，堆不会产生k个项目的排序列表，但是可以在O(k log k)中完成，这很容易。
同样，对于找到最大的k个项目，您可以执行相同的操作，在这种情况下，您将使用最小堆。