一种优化的算法来生成不同的数组
一种优化的算法来生成不同的数组
提问于 2013-07-04 16:03:16
我正在寻找一种优化的算法，它可以给出我编写的结构的数组(或列表)，并删除重复的元素并返回它。
我知道我可以用一个复杂度为O(n^2)的简单算法来做这件事；但我想要一个更好的算法。
任何帮助都将不胜感激。
回答 4
Stack Overflow用户
回答已采纳
发布于 2013-07-04 16:34:43
对于实际使用，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个distinct元素和n个总元素，则此算法将占用O(d)内存和O(n)时间。
由于该算法使用哈希集，因此需要分布良好的哈希才能实现O(n)运行时。如果哈希值很差，运行时可能会退化为O(n*d)
Stack Overflow用户
发布于 2013-07-04 16:10:44
它的运行时间接近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)算法。
Stack Overflow用户
发布于 2013-07-04 16:07:37
您可以在O(NlogN)时间内对数组进行排序，并比较相邻元素以擦除重复元素。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17464934
复制相关文章
相似问题
腾讯云开发者
