Re: [tlug] array duplicate check [C]

[Sigurd Urdahl <sigurdur@example.com>]

Nguyen Vu Hung wrote:
> Hi list,
>
> Excuse my elementary question :D
>
> I have two integer arrays  of size N and M and I want to check if none
> of the elements in the first arrays are contained in the second array.
> The programming language is pure C so no vector or set like Java.
It's been a long while since I last looked at algorithmic efficency, but 
if you can sort the arrays I believe the most efficent comparison would 
be walking both arrays in paralell:

You have

arr_A    # The arrays
arr_B

M   # size of array A
N   # ..and B

ind_A=0   # The "walker"
ind_B=0

end_A=0   # flag indicating we are at the end of this array.
end_B=0

while not ( end_A==1 and end_B==1)
   # First check if we have found the same element in both
   if
       arr_A(ind_A) == arr_B(ind_B) then print "We have the same 
element in both"
   # Then "walk" upwards in the array with the lowest value of the element
   if
       arr_A(ind_A) < arr_B(ind_B) then ind_A++
   else   
       ind_B++

   # Make sure we don't walk past the end of the array
   if ind_A>M then (ind_A = M  ; end_A=1)
   if ind_B>N then (ind_B = N  ; end_B=1)
end while 

This should give you
   O=M*log(M) + N*log(N)
for the sorting, and
   O=M+N
for the comparison if I remember correctly.

kind regards,
-sig

--
Sigurd Urdahl
Linux, goofing, cooking, making fire, computer security, having a
beer. Give me good music.