在列表的列表中查找重复项

让我们努力取得最好的成绩。如果n是列表的数目,m是列表的长度,那么我们可以得到O(n) logn+n)加上哈希码在不同列表中相等的概率。

1. 计算哈希码*
2. 把它们分类
3. 翻一翻单子找出被骗者

*这是重要的一步。对于simlicity,可以将哈希计算为=。。。^(列表[i]<<i)^(列表[i+1]<<(i+1))

对于那些认为PLINQ可以促进事情,但不是好算法的人来说。PLINQ也可以添加到这里,因为所有的步骤都很容易并行化。

我的代码:

static public void Main()
{
    List<List<int>> list = new List<List<int>>(){
      new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
      new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
      new List<int>() {0 ,1 ,4, 2, 4, 5, 6 },
      new List<int>() {0 ,3 ,2, 5, 1, 6, 4 }
    };
    var hashList = list.Select((l, ind) =>
    {
        uint hash = 0;
        for (int i = 0; i < l.Count; i++)
        {
            uint el = (uint)l[i];
            hash ^= (el << i) | (el >> (32 - i));
        }
        return new {hash, ind};
    }).OrderBy(l => l.hash).ToList();
    //hashList.Sort();
    uint prevHash = hashList[0].hash;
    int firstInd = 0;            
    for (int i = 1; i <= hashList.Count; i++)
    {
        if (i == hashList.Count || hashList[i].hash != prevHash)
        {
            for (int n = firstInd; n < i; n++)
                for (int m = n + 1; m < i; m++)
                {
                    List<int> x = list[hashList[n].ind];
                    List<int> y = list[hashList[m].ind];
                    if (x.Count == y.Count && x.SequenceEqual(y))
                        Console.WriteLine("Dupes: {0} and {1}", hashList[n].ind, hashList[m].ind);
                }                    
        }
        if (i == hashList.Count)
            break;
        if (hashList[i].hash != prevHash)
        {
            firstInd = i;
            prevHash = hashList[i].hash;
        }
    }
}

除非您正在做一些非常繁重的工作,否则以下简单的代码可能适合您:

var lists = new List<List<int>>()
{
   new List<int>() {0 ,1, 2, 3, 4, 5, 6 },
   new List<int>() {0 ,1, 2, 3, 4, 5, 6 },
   new List<int>() {0 ,1, 4, 2, 4, 5, 6 },
   new List<int>() {0 ,3, 2, 5, 1, 6, 4 }
};

var duplicates = from list in lists
                 where lists.Except(new[] { list }).Any(l => l.SequenceEqual(list))
                 select list;

(另外,由于LINQ的强大功能,通过向上述代码添加一个.AsParallel()调用,该算法将在多个内核上运行,因此运行速度可能比本线程中提到的复杂、手工调整的解决方案更快。)

类似的操作将为您提供正确的结果:

List<List<int>> list = new List<List<int>>(){
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,4, 2, 4, 5, 6 },
  new List<int>() {0 ,3 ,2, 5, 1, 6, 4 }
};

list.ToLookup(l => String.Join(",", l.Select(i => i.ToString()).ToArray()))
    .Where(lk => lk.Count() > 1)
    .SelectMany(group => group);

算法:

Create a custom hashtable (dictionary: hash -> list of lists)
For each list
  Take a hash of the list (one that takes order into account)
  Search in hashtable
  If you find matches for the hash
    For each list in the hash entry, re-compare the tables
      If you find a duplicate, return true
  Else if you don't find matches for the hash
    Create a temp list
    Append the current list to our temp list
    Add the temp list to the dictionary as a new hash entry
You didn't find any duplicates, so return false

我有一些示例代码。缺少的位是:

• 一个优化,使我们只做一次字典查找每个列表(搜索和插入)。可能需要创建自己的字典/哈希表类才能做到这一点?
• 一个更好的散列算法,您可以根据您的数据分析一堆散列算法

代码如下:

public bool ContainsDuplicate(List<List<int>> input)
{
    var encounteredLists = new Dictionary<int, List<EnumerableWrapper>>();

    foreach (List<int> currentList in input)
    {
        var currentListWrapper = new EnumerableWrapper(currentList);
        int hash = currentListWrapper.GetHashCode();

        if (encounteredLists.ContainsKey(hash))
        {
            foreach (EnumerableWrapper currentEncounteredEntry in encounteredLists[hash])
            {
                if (currentListWrapper.Equals(currentEncounteredEntry))
                    return true;
            }
        }
        else
        {
            var newEntry = new List<EnumerableWrapper>();
            newEntry.Add(currentListWrapper);
            encounteredLists[hash] = newEntry;
        }
    }

    return false;
}

sealed class EnumerableWrapper
{
    public EnumerableWrapper(IEnumerable<int> list)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        this.List = list;
    }

    public IEnumerable<int> List { get; private set; }

    public override bool Equals(object obj)
    {
        bool result = false;

        var other = obj as EnumerableWrapper;
        if (other != null)
            result = Enumerable.SequenceEqual(this.List, other.List);

        return result;
    }

    public override int GetHashCode()
    {
        // Todo: Implement your own hashing algorithm here
        var sb = new StringBuilder();
        foreach (int value in List)
            sb.Append(value.ToString());
        return sb.ToString().GetHashCode();
    }
}

下面是一个潜在的想法(假设值是数字):

实现一个比较器,将每个集合的每个成员乘以其索引,然后求和:

Value:    0  5  8  3  2  0  5  3  5  1
Index:    1  2  3  4  5  6  7  8  9  10
Multiple: 0  10 24 12 10 0  35 24 45 10

成员校验和:170

如果重复数据非常罕见或非常常见,您也可以尝试概率算法。e、 通用航空公司 bloom filter

写你自己的列表比较器怎么样:

class ListComparer:IEqualityComparer<List<int>>
{
     public bool Equals(List<int> x, List<int> y)
     {
        if(x.Count != y.Count)
          return false;

        for(int i = 0; i < x.Count; i++)
          if(x[i] != y[i])
             return false;

       return true;
     }

     public int GetHashCode(List<int> obj)
     {
        return base.GetHashCode();
     }
}

var nonDuplicatedList = list.Distinct(new ListComparer());
var distinctCount = nonDuplicatedList.Count();

如果它们都是一位数,并且元素的数量相同,那么可以将它们放在一起,第一个是123456,并检查数字是否相同。

这是更容易检查重复,如果个别成员可以超过10你将不得不修改这个。

for(int i = 0; i< list.length; i++)
{
    List<int> tempList = list[i];
    int temp = 0;
    for(int j = tempList.length - 1;i > = 0; j--)
    {
        temp = temp * 10 + tempList[j];
    }
    combinded.add(temp);
}

for(int i =0; i< combined.length; i++)
{
    for(int j = i; j < combined.length; j++)
    {
        if(combined[i] == combined[j])
        {
            return true;
        }
    }
}
return false;

这里已经有很多很好的解决方案,但我相信这一个会一直运行得最快 除非 有些数据结构你还没有告诉我们。

• 创建一个从整型键到列表的映射,以及一个从键到列表的映射 List<List<int>>
• 对于每个 List<int> ,使用一些简单的函数计算散列,如 (...((x0)*a + x1)*a + ...)*a + xN) 可以递归计算; a 应该是类似于1367130559的东西(也就是说,某个大素数随机不接近任何有趣的2次方。
• 如果哈希不存在,则将它和它来自的列表作为键值对添加。如果确实存在,请查看第二张地图。如果第二个映射具有该键,则附加新的 到累积列表。如果不是的话,那就走吧 列表<内部> 列表<内部> 您正在测试,并在第二个映射中添加一个新条目,其中包含这两个项的列表。
• 重复这个步骤,直到你看完第一张单子。现在您有了一个包含潜在冲突列表的hashmap(第二个映射),和一个包含键列表的hashmap(第一个映射)。
• 列表<列表<内部>>
• 加 第二个hashmap中每个条目的(块数-1)之和。
• 你的重复项目数就是这两个数字的差(如果你想的话,你可以找到各种各样的其他东西)。

如果您有N个非重复项,并且M个项是K个项中的重复项,那么您需要O(N+M+2K)来创建初始哈希映射,最坏的情况是O(M logm)来进行排序(可能更像O(M log(M/K)),O(M)来进行最终的相等性测试。

C# 3.0: Need to return duplicates from a List<> 它向您展示了如何从列表中返回重复项。

var duplicates = from car in cars
             group car by car.Color into grouped
             from car in grouped.Skip(1)
             select car;