Algorithmus zur Bestimmung, ob 2 Arrays disjunkt sind

Question

Geben Sie einen randomisierten erwarteten linearen Algorithmus mit idealen Hashfunktionen an, der bestimmt, ob zwei Arrays A [1..n] und B [1..n] disjunkt sind, dh ob kein Element von A ist auch ein Element von B.

Kann mir jemand zeigen, wie man das macht oder überhaupt darüber nachdenkt?

Answer 1

for element in a: 
    hasha{element} = 1 

for element in b: 
    if hasha{element} == 1: 
    print element "found in both" 

Zeit: O (len (a) + len (b))