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

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

最佳答案

更新:-独特与独特

如果您正在寻找“唯一”的值(就像您多次看到元素“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的大小。

关于algorithm - 如何在线性时间内计算列表中的不同值？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13865094/