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
VIQR Standard:

Home | Main Index | Thread Index

Home Page Mailing List Linux and Japan TLUG Members Links