algorithm - 在 O(mlogn) 时间内计算两个未排序数组的并集和交集

Question

好的，所以我需要设计以下算法(无需代码，只需几步):

给定两个集合 A和 B长度m和 n每组中的数字分别是不同的、未排序的和 m<n .计算两个集合的交集和并集，结果中没有任何重复值。该算法应在 O(mlog(n)) 时间内运行。

我真的很难找出具有如此时间复杂度的算法。最初，我想连接两个未排序的数组，然后对其执行合并排序并删除重复项，但这远远超过了很多复杂性。

Answer 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 中查找元素在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))