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

Question

我可以考虑对它们进行排序，然后逐个元素检查，但这样的时间复杂度是nlogn。有没有一种线性方法来计算列表中不同元素的数量？

- polerto

Answer 1

更新：- distinct vs. unique

---

如果你正在寻找唯一值（例如，如果你看到一个元素“JASON”出现了不止一次，则它不再是唯一的，不应计算），那么可以使用HashMap在线性时间内完成；）

（通用/语言无关的想法是哈希表）

HashMap /哈希表的每个条目都是<KEY, VALUE>对，其中键是唯一的（但对应于其对中的值没有限制）

步骤1：

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

• 对于列表中看到的每个元素，请检查它是否已经存在于HashMap中O(1)，摊销
  • 如果不存在，请将其添加到HashMap中，其中元素的值作为KEY，您迄今为止看到此值的次数作为VALUE O(1)
  • 如果存在，请将您迄今为止看到此KEY的次数递增O(1)

步骤2：

遍历HashMap并计算VALUE等于1（因此唯一）的KEYS的数量O(n)

分析：

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

---

如果你想要筛选出独特的值（比如你想数一下有多少个不同的元素），那么使用HashSet而不是HashMap/散列表，然后查询HashSet的大小即可。

- sampson-chen

---

这是如何在列表中找到唯一值的数量，问题是要找到不同值的数量。要计算不同值，请使用HashSet。只需将列表的每个元素添加到HashSet中并检查其基数即可。 - user1871166

在第二步中，您是否想要计算HashMap中的所有值，而不仅仅是那些值为1的值？这样做只会计算出现一次的元素，例如列表{PAT，PAT，STEVE，JOEL}将导致值为2（只有STEVE和JOEL出现一次），而不是正确的3个不同名称的值。 - Jason

注意！这里存在一个解释上的差异：我的假设是，如果您看到一个特定的值2次或更多次，它就不再是“独特”的/“唯一”的 - 但我会进行编辑以使其更加清晰。 - sampson-chen

这个算法是摊还的，所以它并不能保证 O(n) 对吧？它也有可能在最坏情况下运行时间为 O(n^2) 对吧？ - polerto

@polerto，使用任何合理的HashMap / Hashtable实现（例如Java库中的实现），您可以假设运行时间为O(n)。 - sampson-chen

使用HashMap无法在线性时间内完成此操作，因为可能存在冲突。如果存在冲突，则即使在映射中查找也可能具有复杂度O(n)，如果每个对象具有相同的哈希值。 - SpaceTrucker

Answer 2

您可以将这个极其酷炫的O(n)时间复杂度和O(1)空间复杂度的原地算法应用于计算不同值的任务 - 只需在最终的O(n)遍历中计算等于哨兵值的值的数量，并从列表的大小中减去该数量。

- j_random_hacker

Answer 3

将列表中的每个元素添加到 HashSet 中，然后检查 HashSet 的 size（基数），即列表中不同值的数量。

- user1871166