algorithm - 确定两组数字是否不相交的有效算法

Question

练习软件开发人员面试并卡在一道算法题上。

Given two sets of unsorted integers with array of length m and other of 
length n and where m < n find an efficient algorithm to determine if 
the sets are disjoint. I've found solutions in O(nm) time, but haven't 
found any that are more efficient than this, such as in O(n log m) time.

Answer 1

使用具有 O(1) 查找/插入的数据结构，您可以轻松地插入第一组的所有元素。

然后foreach第二个集合中的元素，如果存在则不相交，否则不相交

伪代码

function isDisjoint(list1, list2)
    HashMap = new HashMap();
    foreach( x in list1)
        HashMap.put(x, true);

    foreach(y in list2)
        if(HashMap.hasKey(y))
             return false;
    return true;

这会给你一个 O(n + m) 的解决方案