CODEWITHSUNDEEP
c#
Howard
Howard

Reputation: 3758

Find values that overlap in two arrays efficiently and save them out in a third array

Assuming I have the 2 arrays...

string[] a = {"a", "b", "c", "d", "e", "f", "h", "i", "j", "k"};
string[] b = {"a", "c", "d", "e", "g"};
string[] c;

I want to create a resulting array c which has a list of the values that overlap. So for the above I would get the following result:

c = {"a", "c", "d", "e"};

How can I do this efficiently?

Upvotes: 3

Views: 3313

Answers (2)

Jon Skeet
Jon Skeet

Reputation: 1504122

The simplest way - which is also efficient - is to use LINQ's Intersect method:

c = a.Intersect(b).ToArray();

This will use a HashSet<T> internally to keep track of values which can still be returned. See my Edulinq blog post on Intersect for more details.

Note that the result is effectively a set - the order isn't guaranteed (although in practice it will be the order the elements appear in a) and each value will only occur once, even if it's repeated in both original arrays.

Note that if you only need to iterate over the result, it would be more efficient not to turn it into an array at all:

IEnumerable<string> intersection = a.Intersect(b);

EDIT: To find the indexes, you could either do some trickery with LINQ, or just do it fairly simply iteratively:

HashSet<string> remaining = new HashSet<string>(b);
List<Tuple<string, int>> pairs = new List<Tuple<string, int>>();
for (int i = 0; i < a.Length; i++)
{
    if (remaining.Remove(a[i]))
    {
        pairs.Add(Tuple.Of(a[i], i));
    }
}

Upvotes: 8

p.s.w.g
p.s.w.g

Reputation: 149108

The Intersect method in Linq does what you need.

 c = a.Intersect(b).ToArray();

Upvotes: 2

Related Questions