我们希望找到阵列中最小，第3小，第5小和第7小的n个元素

Question

如何在3n + o（n）比较中完成？

我试图采用大小为7的数组（a [6]）并遍历给定的数组。然后按照排序顺序将元素插入到[]中（在第一个7之后的每个插入的6log（6）比较和之前的o（6））。所以总比较= n-7（7log（7））+ 6（ 6 + 1）/ 2比我想要的要大。有人可以描述一种算法来解决这个问题吗？

Answer 1

让我们遍历输入数组A，并在每次迭代时保持包含7个最小元素的排序数组smallest：

smallest = [INF, INF, INF, INF, INF, INF, INF]
for each Number in A
    find the insert position of the Number (if any) in the smallest array with binary 
        search (3 comparisons)
    insert to the smallest if needed (0 comparisons)

最后，我们有7个最小的元素，比较的总数是3*n。

如果我们没有INF模拟元素，我们可以采取前7个元素并对它们进行排序（这种类型是O(1)），然后遍历数组的剩余部分。在这种情况下，比较次数等于(n-7)*3 + O(1) = 3*n + O(1)

Answer 2

您可以使用QuickSelect算法（https://en.wikipedia.org/wiki/Quickselect）。平均运行时间为O（n）。

• 没有，也没有时间限制，但比较次数应在3n + o（n）之内。
• 它可以使用任何数量的空间和时间。

您还提到，只要您满足比较要求的数量，就没有时间要求。有一些排序算法可以进行零元素比较。如果您的数据是整数，则可以使用Radix Sort（https://en.wikipedia.org/wiki/Radix_sort）。