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

Question

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

Answer 1

正如vivek_23所说，使用哈希表的概率很高。

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

因此，对于A∪B，您可以在O(m) A 复制到新的集合C 中em>时间。然后对于 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) 时间内完成所有操作。