如何在线性时间内计算列表中的不同值？

Question

我可以考虑对它们进行排序,然后逐个遍历每个元素,但这是nlogn.是否有线性方法来计算列表中的不同元素？

Answer 1

更新: - 独特与独特

如果您正在寻找"独特"值(如果您不止一次看到"JASON"元素,那么它不再是唯一的,不应该被计算在内)

您可以使用HashMap以线性时间执行此操作;)

(广义/语言不可知的想法是哈希表)

HashMap/Hash表的每个条目都是<KEY, VALUE>对,其中键是唯一的(但对其对应的值没有限制)

步骤1:

迭代列表中的所有元素一次:O(n)

• 对于列表中看到的每个元素,检查它是否已经在HashMap中已经O(1),摊销
  • 如果没有,将它添加到HashMap中,列表中元素的值为KEY,以及您看到此值到目前为止的值O(1)
  • 如果是这样,增加你到目前为止看到这个KEY的次数O(1)

第2步:

迭代HashMap并计算KEYS,其VALUE等于1(因此是唯一的)O(n)

分析:

• 运行时:O(n),摊销
• 空格:O(U),其中U是不同值的数量.

但是,如果您正在寻找"不同"值(如果您想要计算有多少不同的元素),请使用HashSet而不是HashMap/Hash表,然后简单地查询HashSet的大小.