Mailing List Archive


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

[tlug] array duplicate check [C]



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.

Intuitively, the pseudo code will looks like

for i = 1 to N
for j = 1 to  M
if a[i] in b[j] then fail
end for
end for

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

So how can I improve the algorithm? ( for the worst case ) I have a
feeling that I can reduce the complexity to N or M...

Any helps are appreciated.

--
Best Regards,
Nguyen Hung Vu
vuhung16plus{remove}@example.com
VIQR Standard: http://vi.i18n.kde.org/viqr
http://www.flickr.com/photos/vuhung/tags/fav/


Home | Main Index | Thread Index

Home Page Mailing List Linux and Japan TLUG Members Links