能否在O(n)时间复杂度内统计列表中所有最小元素的个数？

可以实现单次遍历、严格O(n)时间复杂度的解法，思路如下：
遍历列表过程中同时维护两个临时变量：current_min 记录当前遍历到的最小元素值，count 记录当前最小值出现的次数。遍历每一个元素时按照规则更新两个变量即可：

• 若当前元素 < current_min：说明找到了更小的新最小值，将current_min更新为当前元素，同时将count重置为1
• 若当前元素 == current_min：直接将count加1
• 若当前元素 > current_min：不做任何处理，继续遍历下一个元素

该方法仅需要遍历列表一次，空间复杂度为O(1)，不需要额外的存储开销，处理长列表时的实际运行效率高于两次遍历的解法。

补充说明：你之前提到的两次遍历解法时间复杂度标注为O(2n)，实际在算法时间复杂度的定义中，常数系数会被忽略，所以也属于O(n)时间复杂度范畴，但你要求的单次遍历方案确实可以减少一次遍历的开销。

以下是Python的实现示例：

def count_min_elements(nums: list) -> int:
    # 处理空列表的边界情况
    if not nums:
        return 0
    current_min = nums[0]
    count = 1
    # 从第二个元素开始遍历
    for num in nums[1:]:
        if num < current_min:
            current_min = num
            count = 1
        elif num == current_min:
            count += 1
    return count

# 用你提供的示例测试
test_list = [1, 2, 3, 1, 1, 5, 2, 1]
print(count_min_elements(test_list)) # 输出结果为4

内容的提问来源于stack exchange，提问作者AndW