Mailing List Archive


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [tlug] array duplicate check [C]



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.



Home | Main Index | Thread Index

Home Page Mailing List Linux and Japan TLUG Members Links