Compare two arrays or arraylists, find similar and different values

Question

I have two arrays (or arraylists, if simpler) of strings. I need to compare them, find which exist only in the first array, which exist in both, and which exist only in the second array. These arrays have different lengths and can be in different orders. If necessary, I suppose I could sort them ...

I know that I could hack this together, but I think it can have a pretty standard and efficient / “best” solution, and I'm most curious.

I use C # for this, but if you want to write your solution in another language, any help is appreciated.

Thanks for the help!

Answer 1

var onlyinfirst = from s in list1 where !list2.Contains(s) select s; var onlyinsecond = from s in list2 where !list1.Contains(s) select s; var onboth = from s in list1 where list2.Contains(s) select s; 

Answer 2

If the arrays are large, then you will want to use a data structure that is efficient for these operations; no arrays.

The naive solution is O (n ^ 2) in time if the arrays are of size n.

If you sort arrays in place, you can binary search for them for elements; sorting is likely to be O (n lg n) and a search n times at a cost of lg n to search will also be O (n lg n) in time.

If you first convert each array to a HashSet<T> , then you can do this in O (n) and O (n) extra space.