2

练习软件开发人员面试并被困在算法问题上。

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.
4

4 回答 4

9

使用具有 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) 解决方案

于 2014-07-08T19:47:28.763 回答
4

相当明显的方法 - 对长度数组进行排序m- O(m log m)。对于 length 数组中的每个元素n，使用二分查找来检查它是否存在于 length m- O(log m)per element=数组中O(n log m)。因为m<n，这加起来O(n log m)。

于 2014-07-08T19:46:47.603 回答
3

看起来 Cheruvian 打败了我，但您可以使用哈希表来获得O(n+m)平均情况：
*将 的所有元素插入m表中，每个元素（可能）花费恒定的时间，假设没有很多相同的哈希值. 这一步是O(m)
*对于 的每个元素n，检查它是否在表中。如果是，则返回 false。否则，继续下一个。这需要O(n).
*如果表中没有，则返回true。

正如我之前所说，这是因为哈希表在平均情况下提供了恒定的查找时间。在极少数情况下，其中的许多唯一元素m具有相同的哈希，这将需要稍长的时间。但是，大多数人不需要关心假设的最坏情况。例如，快速排序比归并排序更常用，因为它提供了更好的平均性能，尽管有O(n^2)上限。

于 2014-07-08T20:03:27.630 回答
2

这是我认为可以回答您的问题的帖子的链接。

3) 排序更小 O((m + n)logm)

  1. 说，m < n，排序 A
  2. 将 B 的每个元素二进制搜索到 A

缺点：修改输入

于 2014-07-08T19:49:52.080 回答