是否有可能在 O(n) 时间内找到列表中的所有最小元素？
Is it possible to find all the smallest elements in a list in O(n) time?
假设我有一个未排序的列表，如下所示：
[1, 2, 3, 1, 1, 5, 2, 1]
并且我想要 return 最小元素的数量（在本例中，min = 1），即 4。
一个快速的解决方案是使用一些内置的 min() 函数找到最小值，然后再次遍历列表并比较值，然后将它们加起来。 O(2n)次。
但我想知道是否有可能在严格的 O(n) 时间内完成 - 只通过列表一次。有办法吗？
请记住，大 O 表示法讨论的是运行时扩展的方式，而不是绝对运行时。从这个意义上说，在数组上进行两次传递且每次都需要时间 O(n) 的算法也具有运行时间 O(n) - 运行时间将随着输入大小的增加而线性扩展。所以你的两遍算法会工作得很好。
一个更严格的要求是您有一个一次性算法，您可以在其中一次看到所有元素。在这种情况下，您可以通过跟踪到目前为止看到的最小数字以及看到它的所有位置来做到这一点。每当您看到一个值时，
- 如果该值大于您看到的最小值，请忽略它；
- 如果该值等于您看到的最小值，则将其添加到位置列表；和
- 如果该值小于您看到的最小值，则丢弃所有最小元素的列表（它们实际上不是最小的）并将其重置为仅包含当前位置的列表。
这也需要时间 O(n)，但一次完成。
假设我有一个未排序的列表，如下所示：
[1, 2, 3, 1, 1, 5, 2, 1]
并且我想要 return 最小元素的数量（在本例中，min = 1），即 4。
一个快速的解决方案是使用一些内置的 min() 函数找到最小值，然后再次遍历列表并比较值，然后将它们加起来。 O(2n)次。
但我想知道是否有可能在严格的 O(n) 时间内完成 - 只通过列表一次。有办法吗？
请记住，大 O 表示法讨论的是运行时扩展的方式，而不是绝对运行时。从这个意义上说，在数组上进行两次传递且每次都需要时间 O(n) 的算法也具有运行时间 O(n) - 运行时间将随着输入大小的增加而线性扩展。所以你的两遍算法会工作得很好。
一个更严格的要求是您有一个一次性算法，您可以在其中一次看到所有元素。在这种情况下，您可以通过跟踪到目前为止看到的最小数字以及看到它的所有位置来做到这一点。每当您看到一个值时，
- 如果该值大于您看到的最小值，请忽略它；
- 如果该值等于您看到的最小值，则将其添加到位置列表；和
- 如果该值小于您看到的最小值，则丢弃所有最小元素的列表（它们实际上不是最小的）并将其重置为仅包含当前位置的列表。
这也需要时间 O(n)，但一次完成。