确定两组数字是否不相交的高效算法

一尘不染

确定两组数字是否不相交的高效算法

algorithm

进行软件开发人员面试的练习，并陷入算法问题。

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.

阅读 241

2020-07-28

共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）解决方案

2020-07-28