gpt4 book ai didi

c++ - C++中两个以上集合的Set_union/Set_intersect

转载 作者:搜寻专家 更新时间:2023-10-31 01:58:31 29 4
gpt4 key购买 nike

我知道这些命令适用于两组。

是否有任何简单快速的方法可以为超过两组的情况执行此操作。

我想我可以为此使用某种循环,但也许有更好的方法。

谢谢

最佳答案

对于集合并集,如果要查看 M 个集合中哪个集合的值最小,则需要进行 M-1 次比较。所以现在我们弹出这个值然后再去。如果 N 是所有集合中的项目总数,我们的算法就是 O(NM)(忽略它对于 Big-O 表示法是 M-1)。

我们可以优化的地方如下:如果我们对每个集合的最低元素进行排序:现在我们从前面弹出一个元素,但是从那个集合中我们只需要 O(logM) 插入到我们新排序的前面.我们对每个项目都这样做,所以我们的算法是 O(N logM)。

请注意,如果您有 3 个,您可能什么也得不到。如果您有 8 个这样的集合,它肯定会显示出 yield 。

对于集合交集,我们只查找出现在所有集合中的值。如果最小值与最大值相同,我们知道它们都是相同的。我们可以弹出并丢弃较小的值(如果不是),然后在每次下一个值时再次插入。如果是这样,我们将添加到结果中,然后从每个列表中弹出。无论哪种方式,我们仍然会有 O(N logM)

关于c++ - C++中两个以上集合的Set_union/Set_intersect,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3948702/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com