5

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

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是节点列表。它在某种程度上做对了，但并不完美。任何人有更好的解决方案？？？

4

4 回答 4

6

您当前的算法是 O(N-squared)，对于大型列表，它的性能会很差。

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

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

如果您可以使用 Linq，只需执行

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

更新

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

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    return source.Distinct(EqualityComparer<TSource>.Default); 
} 

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer) 
{ 
    if (source == null)  
    { 
        throw new ArgumentNullException("source"); 
    } 
    return DistinctImpl(source, comparer ?? EqualityComparer<TSource>.Default); 
} 

private static IEnumerable<TSource> DistinctImpl<TSource>( 
    IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer) 
{ 
    HashSet<TSource> seenElements = new HashSet<TSource>(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/

于 2012-07-17T04:28:02.577 回答
4

这就像一种享受：

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();

再简单不过了。:-)

于 2012-07-17T04:52:01.330 回答
3

小猪支持 Eric J. 的回答...您需要实现 EqualityComparer 以完全控制如何识别不同的项目。

class Program
{
    static void Main(string[] args)
    {
        var list = new List<SampleClass>();
        // add some items

        var distinctItems = list.Distinct(new SampleClass());
    }
}

public class SampleClass : EqualityComparer<SampleClass>
{
    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

于 2012-07-17T04:34:50.570 回答
2

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

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

您正在检查每对节点两次。首先检查 i = 0 和 j = 1 的时间，然后检查 i = 1 和 j = 0 的时间。不需要在 i 之前或等于 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++;
    }
}

您说这可行但并不完美，所以我假设您没有使用标准列表，并且您的节点使用 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++;
    }
}
于 2012-07-17T04:42:26.577 回答