C# 检查两个 List<int> 是否有相同的数字

Check two List<int>'s for the same numbers

提问by Gerrie Schenck

I have two List's which I want to check for corresponding numbers.

我有两个列表，我想检查相应的数字。

for example

例如

List<int> a = new List<int>(){1, 2, 3, 4, 5};
List<int> b = new List<int>() {0, 4, 8, 12};

Should give the result 4. Is there an easy way to do this without too much looping through the lists?

应该给出结果 4. 有没有一种简单的方法来做到这一点，而不会在列表中进行太多循环？

I'm on 3.0 for the project where I need this so no Linq.

我在 3.0 的项目上需要这个，所以没有 Linq。

采纳答案by ljs

You can use the .net 3.5 .Intersect() extension method:-

您可以使用 .net 3.5 .Intersect() 扩展方法：-

List<int> a = new List<int>() { 1, 2, 3, 4, 5 };
List<int> b = new List<int>() { 0, 4, 8, 12 };

List<int> common = a.Intersect(b).ToList();

回答by Otávio Décio

You can sort the second list and loop through the first one and for each value do a binary search on the second one.

您可以对第二个列表进行排序并遍历第一个列表，并为每个值对第二个列表进行二分搜索。

回答by JoshBerke

var c = a.Intersect(b);

var c = a.Intersect(b);

This only works in 3.5 saw your requirement my appologies.

这仅适用于 3.5 看到您的要求我的应用程序。

回答by Chris J

If both lists are sorted, you can easily do this in O(n) time by doing a modified merge from merge-sort, simply "remove"(step a counter past) the lower of the two leading numbers, if they are ever equal, save that number to the result list and "remove" both of them. it takes less than n(1) + n(2) steps. This is of course assuming they are sorted. But sorting of integer arrays isn't exactly expensive O(n log(n))... I think. If you'd like I can throw together some code on how to do this, but the idea is pretty simple.

如果两个列表都已排序，您可以通过从合并排序中进行修改后的合并，在 O(n) 时间内轻松完成此操作，只需“删除”（将计数器移过）两个前导数字中的较小者，如果它们相等，将该数字保存到结果列表中并“删除”它们。它需要少于 n(1) + n(2) 个步骤。这当然是假设它们已排序。但是整数数组的排序并不完全是昂贵的 O(n log(n)) ......我认为。如果您愿意，我可以将一些有关如何执行此操作的代码放在一起，但这个想法非常简单。

回答by Noldorin

The method recommended by ocdecio is a good one if you're going to implement it from scratch. Looking at the time complexity compared to the nieve method we see:

如果您打算从头开始实施，ocdecio 推荐的方法是一种很好的方法。查看与 nieve 方法相比的时间复杂度，我们看到：

Sort/binary search method: T ~= O(n log n) + O(n) * O(log n) ~= O(n log n)

排序/二元搜索方法：T ~= O(n log n) + O(n) * O(log n) ~= O(n log n)

Looping through both lists (nieve method): T ~= O(n) * O(n) ~= O(n ^ 2)

循环遍历两个列表（nieve 方法）：T ~= O(n) * O(n) ~= O(n ^ 2)

There may be a quicker method, but I am not aware of it. Hopefully that should justify choosing his method.

可能有更快的方法，但我不知道。希望这应该证明选择他的方法是合理的。

回答by kirkus

Jeff Richter's excellent PowerCollections has Set with Intersections. Works all the way back to .NET 2.0.

Jeff Richter 出色的 PowerCollections 有 Set with Intersections。一直工作到 .NET 2.0。

http://www.codeplex.com/PowerCollections

http://www.codeplex.com/PowerCollections

        Set<int> set1 = new Set<int>(new[]{1,2,3,4,5});
    Set<int> set2 = new Set<int>(new[]{0,4,8,12});
    Set<int> set3 = set1.Intersection(set2);

回答by Jon Skeet

You could do it the way that LINQ does it, effectively - with a set. Now before 3.5 we haven't got a proper set type, so you'd need to use a Dictionary<int,int>or something like that:

您可以按照 LINQ 的方式有效地进行操作 - 使用一组。现在在 3.5 之前，我们还没有合适的 set 类型，所以你需要使用 aDictionary<int,int>或类似的东西：

• Create a Dictionary<int, int>and populate it from list ausing the element as both the key and the value for the entry. (The value in the entry really doesn't matter at all.)
• Create a new list for the intersections (or write this as an iterator block, whatever).
• Iterate through list b, and check with dictionary.ContainsKey: if it does, add an entry to the list or yield it.

• 创建一个Dictionary<int, int>并a使用元素作为条目的键和值从列表中填充它。（条目中的值实际上根本无关紧要。）
• 为交叉点创建一个新列表（或将其写为迭代器块，无论如何）。
• 遍历列表b，并检查dictionary.ContainsKey：如果是，则向列表中添加一个条目或产生它。

That should be O(N+M) (i.e. linear in both list sizes)

那应该是 O(N+M) （即在两个列表大小中都是线性的）

Note that that will give you repeated entries if list b contains duplicates. If you wanted to avoid that, you could always change the value of the dictionary entry when you first see it in list b.

请注意，如果列表 b 包含重复项，则会为您提供重复条目。如果您想避免这种情况，您可以在第一次在 list 中看到字典条目时更改它的值b。

回答by G Jason Smith

Here is a method that removed duplicate strings. Change this to accomidate int and it will work fine.

这是一种删除重复字符串的方法。将此更改为适应 int 并且它会正常工作。

public List<string> removeDuplicates(List<string> inputList)
    {
        Dictionary<string, int> uniqueStore = new Dictionary<string, int>();
        List<string> finalList = new List<string>();

        foreach (string currValue in inputList)
        {
            if (!uniqueStore.ContainsKey(currValue))
            {
                uniqueStore.Add(currValue, 0);
                finalList.Add(currValue);
            }
        }
        return finalList;

    }

Update: Sorry, I am actually combining the lists and then removing duplicates. I am passing the combined list to this method. Not exactly what you are looking for.

更新：抱歉，我实际上是在合并列表，然后删除重复项。我将组合列表传递给此方法。不完全是你正在寻找的。

回答by aku

In comment to question author said that there will be

在对问题的评论中，作者说会有

Max 15 in the first list and 20 in the second list

第一个列表中最多 15 个，第二个列表中最多 20 个

In this case I wouldn't bother with optimizations and use List.Contains.

在这种情况下，我不会理会优化并使用 List.Contains。

For larger lists hash can be used to take advantage of O(1) lookup that leads to O(N+M) algorithm as Jon noted.

对于较大的列表，散列可用于利用 O(1) 查找导致 O(N+M) 算法，如 Jon 所述。

Hash requires additional space. To reduce memory usage we should hash shortest list.

哈希需要额外的空间。为了减少内存使用，我们应该散列最短列表。

List<int> a = new List<int>() { 1, 2, 3, 4, 5 };
List<int> b = new List<int>() { 0, 4, 8, 12 };
List<int> shortestList;
List<int> longestList;
if (a.Count > b.Count)
{
    shortestList = b;
    longestList = a;
}
else
{
    shortestList = a;
    longestList = b;                
}

Dictionary<int, bool> dict = new Dictionary<int, bool>();
shortestList.ForEach(x => dict.Add(x, true));

foreach (int i in longestList)
{
    if (dict.ContainsKey(i))
    {
        Console.WriteLine(i);
    }
}

回答by Chris S

(Previous answer - changed IndexOf to Contains, as IndexOf casts to an array first)

（上一个答案 - 将 IndexOf 更改为包含，因为 IndexOf 首先转换为数组）

Seeing as it's two small lists the code below should be fine. Not sure if there's a library with an intersection method like Java has (although List isn't a set so it wouldn't work), I know as someone pointed out the PowerCollection library has one.

看到它是两个小列表，下面的代码应该没问题。不确定是否有一个像 Java 那样具有交集方法的库（虽然 List 不是一个集合所以它不起作用），我知道有人指出 PowerCollection 库有一个。

List<int> a = new List<int>() {1, 2, 3, 4, 5};
List<int> b = new List<int>() {0, 4, 8, 12};

List<int> result = new List<int>();
for (int i=0;i < a.Count;i++)
{
    if (b.Contains(a[i]))
        result.Add(a[i]);
}

foreach (int i in result)
    Console.WriteLine(i);

Update 2:HashSet was a dumb answer as it's 3.5 not 3.0

更新 2：HashSet 是一个愚蠢的答案，因为它是 3.5 而不是 3.0

Update: HashSet seems like the obvious answer:

更新：HashSet 似乎是显而易见的答案：

// Method 2 - HashSet from System.Core
HashSet<int> aSet = new HashSet<int>(a);
HashSet<int> bSet = new HashSet<int>(b);
aSet.IntersectWith(bSet);
foreach (int i in aSet)
    Console.WriteLine(i);