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

Question

需要帮助用算法解决这个问题...给定两个集合 A 和 B，分别具有 m 和 n 个元素，来自线性顺序。这些集合不一定是排序的。还假设 m ≤ n。展示如何在 O(nlogm) 时间内计算 A∪B 和 A ∩ B。

标签： algorithmsettime-complexityarray-algorithms

Answer 1

正如 vivek_23 所说，您可以使用高概率的哈希表做得更好。

但是，要实现O(n log m )，并假设您的集合存储为数组，您可以在O(m log m)时间内对A进行排序，然后对B的每个元素进行n二进制搜索以查看它是否也在一个。每次查找需要 O (log m)时间，总共需要O(n log m)时间。

因此，对于A∪B，您可以在O(m)时间内将A复制到新的集合C中。然后对于 B 的每个元素，您在 A 上进行查找（二进制搜索）。如果它不在 A 中，则将其添加到 C。这样，您将花费O(m + n log m)时间来构造C和O(m log m)* 对 A 进行排序。由于m < n，总时间为O(n log m)如您所愿。

对于A ∩ B，您将从空集D开始。对于B的每个元素，您在A中进行查找。如果它在那里，您将其添加到D。完成后，您将在A上完成n次查找，总共(n log m)。

如果要将列表 A 的所有元素插入哈希表而不是对它们进行排序，则可以在O(m + n)时间内以高概率完成所有操作。