c# - 制作不同数组的优化算法

Question

<分区>

Answer 1

对于实际使用，LINQ 的 Distinct 是最简单的解决方案。它使用基于哈希表的方法，可能与以下算法非常相似。

如果您对这样的算法感兴趣:

IEnumerable<T> Distinct(IEnumerable<T> sequence)
{
    var alreadySeen=new HashSet<T>();
    foreach(T item in sequence)
    {
        if(alreadySeen.Add(item))// Add returns false if item was already in set
            yield return;
    }
}

如果有 d 个不同的元素和 n 个元素，那么这个算法将占用 O(d) 内存和 O( n) 时间。

由于此算法使用哈希集，因此需要分布良好的哈希来实现 O(n) 运行时。如果散列很糟糕，运行时可能会退化为 O(n*d)