在 n 个项目的数组中找到 k 个最小数字的算法 [英] Algorithm to find k smallest numbers in array of n items

问题描述

我正在尝试编写一种算法，该算法可以在 O(n) 时间内打印 n 大小数组中的 k 个最小数字，但我无法将时间复杂度降低到 n.我该怎么做?

I'm trying to write an algorithm which can print the k smallest numbers in an n-size-array in O(n) time, but I cannot reduce the time complexity to n. How can I do this?

推荐答案

我之前在一次采访中做过这个，最优雅/最有效的方法之一是

I've done this in an interview before, and one of the most elegant/efficient ways to do this is

O(n log k). 
with space: O(k) (thanks, @Nzbuu)

基本上，您将使用大小限制为 k 的最大堆.对于数组中的每个项目，检查它是否小于最大值(仅 O(1)).如果是，删除最大值并将其放入堆中(O(log k)).如果它更大，请转到下一项.

Basically you're going to use a max-heap of size limited to k. For each item in the array, check to see if it's smaller than the max (only O(1)). If it is, remove the max and put that in the heap (O(log k)). If its bigger, go to the next item.

当然，堆不会产生 k 个项目的排序列表，但这可以在 O(k log k) 中完成，这很容易.

Of course, the heap doesn't yield a sorted list of k items, but that can be done in O(k log k) which is easy.

类似地，您可以用同样的方法找到最大的 k 个项目，在这种情况下，您将使用最小堆.

Similarly, you can do the same for finding the largest k items, in which case you would use a min-heap.

这篇关于在 n 个项目的数组中找到 k 个最小数字的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！