如何在线性时间内计算列表中的不同值? [英] How to count distinct values in a list in linear time?

问题描述

我可以考虑对它们进行排序，然后一个一个地检查每个元素，但这是 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)

您可以使用 在线性时间内完成此操作哈希映射 ;)

(广义/语言不可知的想法是哈希表)

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

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

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，以列表中元素的值作为KEY，以及到目前为止你看到这个值的次数为VALUEO(1)
  • 如果是，请增加您目前看到此 KEY 的次数O(1)

  步骤 2:

  遍历 HashMap 并计算 VALUE 恰好等于 1(因此唯一)的 KEYS 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 是不同值的数量.

  但是，如果您正在寻找 distinct" 值(例如，如果您想计算有多少不同 元素)，请使用 HashSet 而不是 HashMap/Hash 表，然后简单地查询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.

  这篇关于如何在线性时间内计算列表中的不同值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！