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

Question

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?

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

Answer 1

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

Answer 2

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

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

Answer 3

var c = a.Intersect(b);

This only works in 3.5 saw your requirement my appologies.

Answer 4

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.

Answer 5

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:

Sort/binary search method: 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)

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

Answer 6

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

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

Answer 7

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 or something like that:

• Create a Dictionary and populate is from list a using 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.

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

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.

Answer 8

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

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.

Answer 9

In comment to question author said that there will be

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

In this case I wouldn't bother with optimizations and use 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.

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

Answer 10

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

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.

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

Update: HashSet seems like the obvious answer:

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

Answer 11

Tested on 3.0

    List<int> a = new List<int>() { 1, 2, 3, 4, 5, 12, 13 };
    List<int> b = new List<int>() { 0, 4, 8, 12 };
    List<int> intersection = new List<int>();
    Dictionary<int, int> dictionary = new Dictionary<int, int>();
    a.ForEach(x => { if(!dictionary.ContainsKey(x))dictionary.Add(x, 0); });
    b.ForEach(x => { if(dictionary.ContainsKey(x)) dictionary[x]++; });
    foreach(var item in dictionary)
    {
        if(item.Value > 0)
            intersection.Add(item.Key);
    }