是否有可能在 O(n) 时间内找到列表中所有最小的元素？

Question

假设我有一个未排序的列表，如下所示：

[1, 2, 3, 1, 1, 5, 2, 1]

我想返回最小元素的数量（在本例中，min = 1），即 4。

一个快速的解决方案是使用一些内置函数找到最小值min()，然后再次迭代列表并比较值，然后对它们进行计数。O(2n)时间。

但我想知道是否可以在严格的O(n)时间内做到这一点 - 只通过列表一次。有办法这样做吗？

Answer 1

请记住，大 O 表示法讨论的是运行时扩展的方式，而不是绝对运行时。从这个意义上说，对数组进行两次传递且每次花费时间为 O(n) 的算法也具有运行时间 O(n) - 运行时间将随着输入大小的增加而线性扩展。所以你的两遍算法就可以正常工作。

更强烈的要求是您有一个一次性算法，您可以在其中一次查看所有元素。在这种情况下，您可以通过跟踪到目前为止您所看到的最小数字以及您所看到的所有位置来做到这一点。每当你看到一个值时，

• 如果该值大于您见过的最小值，请忽略它；
• 如果该值等于您见过的最小值，则将其添加到位置列表中；和
• 如果该值小于您见过的最小值，则丢弃所有最小元素的列表（它们实际上不是最小的）并将其重置为仅包含当前位置的列表。

这也需要时间 O(n)，但只需一次即可完成。