我们想要找到一个数组中n个元素中最小的，第三个最小的，第五个最小的和第七个最小的

Question

如何在3n + o(n)比较范围内做到这一点呢？

我尝试获取一个大小为7 (a6)的数组，并遍历给定的数组。然后按排序顺序在a[]中插入元素(6log(6)次比较，前7次插入，o(6)次).So总比较= 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)。

• None也没有时间限制，但比较次数应该在3n+o(N)之内。
• 它可以使用任意数量的空间和时间。

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