我可以考虑对它们进行排序，然后逐个检查每个元素，但这是 nlogn。是否有一种线性方法来计算列表中的不同元素？
问问题
11273 次
3 回答
11
更新： - 独特与独特
如果您正在寻找“唯一”值（例如，如果您多次看到一个元素“JASON”，则它不再是唯一的，不应计算在内）
您可以使用HashMap在线性时间内做到这一点；）
（广义/与语言无关的想法是Hash table）
HashMap / Hash 表的每个条目都是<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 / Hash 表，然后简单地查询 HashSet 的大小。
于 2012-12-13T17:22:52.547 回答
1
您可以调整这个非常酷的 O(n) 时间和 O(1) 空间就地算法来删除重复值，以完成计算不同值的任务——只需计算等于最终 O 中的哨兵值的值的数量(n) 通过，并从列表的大小中减去它。
于 2012-12-13T17:46:04.030 回答