我该如何计算两个集合的不相交元素

本文关键字：元素 集合 两个 何计算 计算 | 更新日期: 2023-09-27 17:49:32

给定具有相同类型元素的两个集合A和B(有序或无序)，其中A、B或两者中存在任意数量的元素。

我想确定A中的哪些元素不包含在B中，以及B中的哪些元素不包含在A中。

这很容易通过

完成
var dA = A.Except(B);
var dB = B.Except(A);

我的问题:这是这个任务最有效的算法吗?

由于上面迭代了两个集合，因此我们似乎可以重用第一次迭代中的一些信息，以减少在第二次迭代中花费的精力。

我该如何计算两个集合的不相交元素

设n为集合A的大小，m为集合B的大小。如果我们假设A和B被实现为哈希表，那么有一个简单的O(min(n,m))期望时间算法来找到A ' B和B ' A。

W.l.o。g let n < m(否则交换集合).

  1. 遍历A。对于每个元素，检查它是否也在B中。是，从B中移除。否，添加到dA
  2. 我以为会有第二步，但实际上你已经完成了。

结果将在dA和B。

如果你不想破坏B，你可以事先创建它的一个副本，当作为一个简单的memcpy实现时，它应该非常快。

您可以使用持久数据结构来表示B，但这会增加相当大的成本并且不太可能有用，除非您的集合大小非常不平衡。

如果可以按顺序迭代集合，则可以使用合并排序的合并阶段算法:

a = A.First
b = B.First
while a <> Nil and b <> Nil do
if a < b
  dA.Add(a)
  a = A.Next 
else if a > b
   dB.Add(b)
   b = B.Next 
else
   a = A.Next 
   b = B.Next 
endwhile
if a <> Nil
   dA.Add(rest of A)
if b <> Nil
   dB.Add(rest of B)
相关文章：