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

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

ind_A=0   # The "walker"

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

while not ( end_A==1 and end_B==1)
# First check if we have found the same element in both
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
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
for the comparison if I remember correctly.

kind regards,

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