[tlug] array duplicate check [C]

["Stephen J. Turnbull" <stephen@example.com>]

Nguyen Vu Hung writes:

 > whose the complexity is N*M in the worst case. The performance will be
 > a pain if N or M grow big.

You want to ensure the intersection is empty, right?  If at least one
of M and N is small, brute force it.  If they're large, you want a
Bloom filter.  O(N+M) in the average case (which is a minimum for this
problem as you must examine each element of both arrays at least
once).  I don't know offhand how to compute worst case (it might be
O(N*M)), but worst case is incredibly unlikely (and you can adjust
"incredible" to taste).