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

Question

我可以考虑对它们进行排序，然后一个一个地检查每个元素，但这是 nlogn。是否有一种线性方法可以对列表中的不同元素进行计数？

Answer 1

更新:- 独特与独特

---

如果您要查找“唯一” 值(例如，如果您不止一次看到一个元素“JASON”，则它不再是唯一的，不应计算在内)

您可以使用 HashMap 在线性时间内完成此操作;)

(广义/与语言无关的想法是 Hash table )

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

第 1 步:

遍历列表中的所有元素一次:O(n)

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

第二步:

遍历 HashMap 并计算 VALUE 恰好等于 1 的 KEYS(因此唯一)O(n)

分析:

• 运行时间:O(n)，摊销
• 空间:O(U)，其中 U 是不同值的数量。

---

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