0

我正在寻找一种优化算法，该算法提供我编写的结构的数组（或列表），并删除重复的元素并返回它。
我知道我可以通过复杂度为 O(n^2) 的简单算法来做到这一点；但我想要一个更好的算法。

任何帮助将不胜感激。

4

4 回答 4

3

这在接近 O(N) 的时间内运行：

var result = items.Distinct().ToList();

[编辑]

由于没有来自 Microsoft 的文档证明它是 O(N) 时间，因此我使用以下代码进行了一些计时：

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Demo
{
    class Program
    {
        private void run()
        {
            test(1000);
            test(10000);
            test(100000);
        }

        private void test(int n)
        {
            var items = Enumerable.Range(0, n);
            new Action(() => items.Distinct().Count())
                .TimeThis("Distinct() with n == " + n + ": ", 10000);
        }

        static void Main()
        {
            new Program().run();
        }
    }

    static class DemoUtil
    {
        public static void TimeThis(this Action action, string title, int count = 1)
        {
            var sw = Stopwatch.StartNew();

            for (int i = 0; i < count; ++i)
                action();

            Console.WriteLine("Calling {0} {1} times took {2}",  title, count, sw.Elapsed);
        }
    }
}

结果是：

Calling Distinct() with n == 1000:   10000 times took 00:00:00.5008792
Calling Distinct() with n == 10000:  10000 times took 00:00:06.1388296
Calling Distinct() with n == 100000: 10000 times took 00:00:58.5542259

时间与 近似线性增加n，至少对于这个特定的测试，这表明正在使用 O(N) 算法。

于 2013-07-04T08:10:43.580 回答
3

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

如果您对这种算法的外观感兴趣：

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)

于 2013-07-04T08:34:42.953 回答
2

您可以在O(NlogN)时间内对数组进行排序，并比较相邻元素以擦除重复元素。

于 2013-07-04T08:07:36.787 回答
2

您可以使用复杂度为 O(N) 的 HashSet：

List<int> RemoveDuplicates(List<int> input)
{
    var result = new HashSet<int>(input);
    return result.ToList();
}

但它会增加内存使用量。

于 2013-07-04T08:09:32.150 回答