如何在 3n + o(n) 次比较内完成？
我尝试获取一个大小为 7 (a[6]) 的数组并遍历给定数组。然后按排序顺序将元素插入到 a[] 中(前 7 之后的每个插入进行 6log(6) 次比较，之前进行 o(6) 次比较)。所以总比较 = n-7(7log(7))+6( 6+1)/2 这比我想要的要大。有人可以描述解决这个问题的算法吗？
最佳答案
让我们遍历输入数组 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)
关于algorithm - 我们想找到数组中 n 个元素中最小的、第三小的、第五小的和第七小的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47917806/