天道酬勤,学无止境

在集合列表中查找不相交集合对的数量(Find number of pairs of disjoint sets in a list of sets)

问题

问题陈述如下:给定n个集合的列表,每个集合包含k个整数,找到不相交集合对的数量。 假设集合的可能元素是正的并且以 c > n 为界,并且假设 k << n。

我正在尝试提出一种有效的算法来比 O(kn^2) 更快地解决这个问题,这是天真的解决方案的运行时间。

我能想出的最佳策略包括遍历列表中的每个集合,并对集合的元素进行散列处理,以便集合中的每个元素映射到包含它的集合的一组索引。 然后,对于迭代中的当前集合,使用它的 c 个元素作为键,并考虑由哈希表作为值给出的 c 个索引集合的并集。 这个结果集表示到目前为止遇到的与当前集不相交的集的数量,我们可以使用它来查找不相交集的数量。 在整个迭代中对这个值求和会产生正确的答案。 但是,由于联合操作是 O(n),因此这种策略并不比简单的解决方案更好。

这个问题最有效的解决方案是什么?

回答1

由于 k << n,您可以通过以下方式降低复杂度:

  • 对每个集合进行排序,可以是 n * k * log(k)
  • 然后按第一个最后一个元素对所有集合进行排序,n * log(n)

现在比较需要 n * (n - 1) 次操作,它们是:

  • 将 s1.Last 与 s2.First 进行比较(大多数情况下,如 k << n)
  • 或者有效地搜索 s1 s2 交集,在 k 中最大,考虑到 s1 和 s2 已排序

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐