我能想到的对它们进行排序，然后去在每个元素逐个但这是nlogn。有没有算在列表中不同元素的线性方法？

I can think of sorting them and then going over each element one by one but this is nlogn. Is there a linear method to count distinct elements in a list?

推荐答案

更新： - 独特与唯一

如果您正在寻找的独特的值（如，如果你看到一个元素JASON不止一次，比它已不再是唯一的，不应该被计算在内）

If you are looking for "unique" values (As in if you see an element "JASON" more than once, than it is no longer unique and should not be counted)

您可以做到这一点的线性时间使用 HashMap的;）

You can do that in linear time by using a HashMap ;)

（广义/语言无关的想法是哈希表）

(The generalized / language-agnostic idea is Hash table)

一个HashMap /哈希表中的每一项都是＆LT;关键字，值＆GT; 对，其中键是唯一的（但在对他们的相应值没有限制）

Each entry of a HashMap / Hash table is <KEY, VALUE> pair where the keys are unique (but no restrictions on their corresponding value in the pair)

第1步：

遍历列表，一旦所有的元素： O（N）

Iterate through all elements in the list once: O(n)

对于出现在列表中的每个元素，检查，看它是否在HashMap中已 O（1），摊销 如果不是，将其添加到与列表中的关键元素的值，数量HashMap的时候，你已经看到了这个值，只要该值 O（1） 如果是这样，增加你已经看到了这个KEY至今的次数 O（1） For each element seen in the list, check to see if it's in the HashMap already O(1), amortized If not, add it to the HashMap with the value of the element in the list as the KEY, and the number of times you've seen this value so far as the VALUE O(1) If so, increment the number of times you've seen this KEY so far O(1)

第二步：

遍历HashMap中和计数与值的所有键等于正好1（因此唯一的） O（N）

Iterate through the HashMap and count the KEYS with VALUE equal to exactly 1 (thus unique) O(n)

分析：

在运行时：为O（n），摊销 空间：O（U），其中U是不同值的数量。

然而，如果你正在寻找的独特的值（如，如果你想看看有多少的不同的的元素存在），使用的 HashSet的，而不是一个HashMap /哈希表，然后简单地查询的HashSet的大小。

If, however, you are looking for "distinct" values (As in if you want to count how many different elements there are), use a HashSet instead of a HashMap / Hash table, and then simply query the size of the HashSet.