从列表中删除重复值的最佳算法

从列表中删除重复值的最佳算法是什么？ 我试过这个：

for (int i = 0; i < AuthorCounter-1; i++) { for (int j = 0; j < AuthorCounter-1; j++) { if (i != j) { if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[j].Text) { AuthorGroupNode.Nodes[j].Remove(); AuthorCounter--; } } } } 

这里， AuthorGroupNodes是节点上的列表。 它在某种程度上做得对，但并不完美。 谁有更好的解决方案???

Answer 1

您当前的算法是O（N平方），对于大型列表，它的性能非常差。

如果空间不是问题，则可以保留节点哈希值的HashSet 。 遍历列表一次。 如果节点的哈希值在HashSet中，则表示这是一个重复节点。 跳过它。 如果散列不在HashSet中，请将此节点添加到新列表，并将节点的散列添加到HashSet。

这将执行O（N），并且需要内存用于原始列表，列表的副本减去任何重复项，以及HashSet。 该算法是非破坏性的。

如果你可以使用Linq，那就干嘛

 var distinctList = originalList.Distinct().ToList(); 

UPDATE

发现这几乎就是Jon Skeet重新实现Distinct的方式。

 public static IEnumerable Distinct( this IEnumerable source) { return source.Distinct(EqualityComparer.Default); } public static IEnumerable Distinct( this IEnumerable source, IEqualityComparer comparer) { if (source == null) { throw new ArgumentNullException("source"); } return DistinctImpl(source, comparer ?? EqualityComparer.Default); } private static IEnumerable DistinctImpl( IEnumerable source, IEqualityComparer comparer) { HashSet seenElements = new HashSet(comparer); foreach (TSource item in source) { if (seenElements.Add(item)) { yield return item; } } } 

https://codeblog.jonskeet.uk/2010/12/30/reimplementing-linq-to-objects-part-14-distinct/

Answer 2

这就像一种享受：

 var xs = new [] { 2, 3, 2, 4, 3, 3, 5, 6, }; var ys = xs .ToLookup(z => z, z => z) .Select(x => x.First()); 

对于您的代码，它看起来像这样：

 var nodes = AuthorGroupNode.Nodes .ToLookup(z => z.Text, z => z) .Select(x => x.First()) .ToArray(); 

不能比那简单得多。 🙂

Answer 3

小猪退出Eric J.的答案……你会想要实现一个EqualityComparer来完全控制不同物品的识别方式。

 class Program { static void Main(string[] args) { var list = new List(); // add some items var distinctItems = list.Distinct(new SampleClass()); } } public class SampleClass : EqualityComparer { public string Text { get; set; } public override bool Equals(SampleClass x, SampleClass y) { if (x == null || y == null) return false; return x.Text == y.Text; } public override int GetHashCode(SampleClass obj) { if (obj == null) return 0; if (obj.Text == null) return 0; return obj.Text.GetHashCode(); } } 

更多信息： http ： //msdn.microsoft.com/en-us/library/bb338049

Answer 4

你永远不会检查列表的最后一个元素，你的第二个元素需要改为这个才能工作：

 for (int j = 0; j < AuthorCounter; j++) 

您正在检查每对节点两次。 首先你要检查i = 0和j = 1，然后你会检查i = 1和j = 0的时间。没有必要在i之前或之前启动j。 当i = 0时，您的内部循环将删除该元素的所有重复项，因此您知道AuthorGroupNodes.Nodes[0]是唯一的。 下次通过外部循环，您将确保AuthorGroupNodes.Nodes[1]是唯一的。 因此，您可以从j等于i + 1开始，并删除对i == j的检查。 此外，当您删除节点时，j仍将增加到下一个节点。 这将跳过j处的新节点，即你移除的节点之后的节点，所以你应该减少j，或者如果不删除节点则只增加j：

 for (int j = i + 1; j < AuthorCounter;) { if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[j].Text) { AuthorGroupNode.Nodes[j].Remove(); AuthorCounter--; } else { j++; } } 

你说这有效但不完美，所以我假设你没有使用标准List，并且你的节点使用Remove（）方法从列表中处理它们自己的删除。

如果列表按您要比较的字段排序，则可以完全删除内部for循环并删除当前元素的任何重复项，直到找到不同的元素：

 for (int i = 0; i < AuthorCounter-1;) { if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[i + 1].Text) { AuthorGroupNode.Nodes[i].Remove(); AuthorCounter--; } else { i++; } }