python - 使用 O(n) 时间和 O(1) 空间查找最频繁出现的元素

Question

我想在 O(n) 时间和 O(1) 空间中找到列表中最常出现的元素。

第一个解决方案

from collections import Counter
def max_repetitions(elements):
    return max([v for k, v in Counter(elements).items() if v > 1])

空间复杂度为O(n)。我不确定时间复杂度。是O(nlogn)还是O(n)？

第二种解决方案

def max_repetitions(elements):
counter = 0
for k, v in Counter(elements).items():
    if v > 1 and counter < v:
        counter = k
return counter

该解决方案的时间复杂度是多少？是O(nlogn)还是O(n)？

还有其他办法吗？

Answer 1

在这样的简单情况下:要获得时间复杂度，请尝试回答您迭代序列中的元素的次数。

由于您在 collections 模块中使用 Counter 类，这也会影响复杂性，但我们假设它的复杂度为 O(n)。

您要做的唯一其他工作是再次迭代列表，也是 O(n)。时间复杂度为 O(n)，因为它随着元素 n 的数量线性增长。