擅长:python、mysql、java
<p>要记住的一点是,O-符号并不一定告诉你什么算法最快。如果一个算法是O(n logn),而另一个算法是O(n<sup>2</sup>),则存在一些<em>值<em>M</em>,因此第一个算法对于所有n>;<em>M</em>都更快。但是<em>M</em>可能比您需要处理的数据量大得多。在</p>
<p>我提出这个问题的原因是我认为<code>HashSet</code>可能仍然是最好的答案,尽管我必须对其进行分析才能确定答案。假设不允许您设置一个包含1000万个存储桶的哈希表,那么您仍然可以设置一个大小合理的表。假设您可以创建一个表大小为100000的<code>HashSet</code>。这些桶将成为一组对象。如果<em>n</em>是数组的大小,则平均bucket大小将是<em>n</em>/100000。因此,要查看某个元素是否已经在<code>HashSet</code>中,如果没有,则添加该元素将花费固定的时间来计算哈希值,如果存储在线性列表中,则O(<em>n</em>)将搜索存储桶中的元素(*)。从技术上讲,这意味着查找所有重复项的算法是O(<em>n</em><sup>2</sup>)。但是由于<em>n</em>中的一个<em>n</em><sup>2</sup>是一个比数组大小小得多的线性列表,所以对我来说,对于1000万个项目来说,它所花费的时间可能比O(<em>n</em>log<em>n</em>)排序要少得多。在O(<em>n</em>log<em>n</em>)排序变得更快的点上,<em>M</em>的值很可能远远大于这个值。(不过,我只是猜测;要想确定答案,就需要进行一些分析。)</p>
<p>无论如何,我倾向于不使用排序,因为如果您只需要查找重复项,那么排序所做的工作将超过您的需要。你不应该仅仅为了找到重复的元素,而需要把元素排列整齐。这对我来说意味着一种可能不是最好的答案。在</p>
<p>(*)注意,在Java8中,每个bucket中的元素将位于某种搜索树中,可能是红黑树,而不是线性列表中。所以算法仍然是O(<em>n</em>log<em>n</em>),而且可能仍然比排序快得多。在</p>