好的，所以我需要设计以下算法（无需代码，只需步骤）：
给定两个集合A，B长度m分别n为，其中每个集合中的数字是不同的，未排序的，并且m<n. 计算两个集合的交集和并集，在任一结果中都没有任何重复值。该算法应该在 O(mlog(n)) 时间内工作。
我很难找出具有如此时间复杂度的算法。最初，我想连接两个未排序的数组，然后对其执行合并排序并删除重复项，但这超出了很多复杂性。
问问题
1138 次
1 回答
1
我错过了性能要求。解决方案在 中O(n log(m))，而不是在O(m log(n) ).
恕我直言，所需的运行时是不可能的。证据已经在评论中勾勒出来了。基本思想是去极端情况下A单例集。然后性能要求归结为检查给定元素是否包含B在运行时的集合中O(log(|B|))。这是据我所知，但是，只有在B已排序或存在某种索引结构时才有可能B。
解决O(blog(m))方案
正如m<n你可以排序A的结果是As。排序A是O(m log(m)) < O(m log(n) )。
As 在 sorted中找到一个元素O(log(m))。所以你只需要检查每个实例B并确定它是否包含在As.
结果运行时（滥用符号）是
O(n log(n))+ m* O(log(n)) = O(n log(n))+ O(n* log(m))=O(n log(m))
于 2016-03-08T21:08:38.740 回答