Jacka - 1 year ago 81
Ruby Question

# Ruby - Find element not in common for two arrays

I've been thinking about a following problem - there are two arrays, and I need to find elements not common for them both, for example:

``````a = [1,2,3,4]
b = [1,2,4]
``````

`[3]`
.

So far I've been doing it like this:

``````a.select { |elem| !b.include?(elem) }
``````

But it gives me
`O(N ** 2)`
time complexity. I'm sure it can be done faster ;)

Also, I've been thinking about getting it somehow like this (using some method opposite to
`&`
which gives common elements of 2 arrays):

``````a !& b  #=> doesn't work of course
``````

Another way might be to add two arrays and find the unique element with some method similar to
`uniq`
, so that:

``````[1,1,2,2,3,4,4].some_method #=> would return 3
``````

The simplest (in terms of using only the arrays already in place and stock array methods, anyway) solution is the union of the differences:

``````a = [1,2,3,4]
b = [1,2,4]
(a-b) | (b-a)
=> [3]
``````

This may or may not be better than `O(n**2)`. There are other options which are likely to give better peformance (see other answers/comments).

Edit: Here's a quick-ish implementation of the sort-and-iterate approach (this assumes no array has repeated elements; otherwise it will need to be modified depending on what behavior is wanted in that case). If anyone can come up with a shorter way to do it, I'd be interested. The limiting factor is the sort used. I assume Ruby uses some sort of Quicksort, so complexity averages `O(n log n)` with possible worst-case of `O(n**2)`; if the arrays are already sorted, then of course the two calls to `sort` can be removed and it will run in `O(n)`.

``````def diff a, b
a = a.sort
b = b.sort
result = []
bi = 0
ai = 0
while (ai < a.size && bi < b.size)
if a[ai] == b[bi]
ai += 1
bi += 1
elsif a[ai]<b[bi]
result << a[ai]
ai += 1
else
result << b[bi]
bi += 1
end
end
result += a[ai, a.size-ai] if ai<a.size
result += b[bi, b.size-bi] if bi<b.size
result
end
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download