两个集合的不重叠和

让我们通过一个合适的例子来理解这个问题

让我们假设两个集合为 s1={1,2,3,4}，s2={3,4,5,6}

在上面两个集合中，我们需要找出不常见于两者的元素。

在集合 s1 中，我们有 3,4，它们在 s2 集合中也重复出现，因此 3,4 是不考虑的元素。

如果我们移除 3,4 元素，剩余的元素是 1,2,5,6。

让我们再举一个例子，如果集合是 s1={5,6,7,8} 和 s2={9,10,11,12}

在上面两个集合中，集合 1 中没有元素与集合 2 的元素相同。

所以，没有元素重复。

现在，我们需要编写代码来找出未重复的数字并打印它们。

首先，让我们讨论这个解决方案的暴力方法。

代码

输出

让我们讨论代码的工作原理

首先，我们需要输入两个集合的大小和两个集合的元素。

上述代码行将获取集合大小和两个集合元素的输入。

获取输入后，我们需要找出两个集合的非重叠元素。

我们如何找到非重叠元素？

找到重叠元素很简单，即对于集合 1 中的一个元素，我们需要在整个第二个集合（即集合 2）中搜索该元素。

让我们通过一个例子来理解这一点。

如果集合 1 是 {1,2,3,4}，第二个集合是 {3,4,5,6}

现在，对于集合 1 中的每个元素，即从 1 开始，我们需要检查 1 是否存在于第二个集合中。

而 1 不存在于第二个集合中，所以 1 是一个非重叠元素，所以我们打印该值。同样，我们需要在集合 2 中检查集合 1 的元素。

接下来，我们有 3，我们将检查 3 是否存在于第二个集合中。它存在于集合中，所以它是一个重叠元素，不打印该元素。

完成集合 1 的所有元素后，我们需要检查集合 2 的所有元素，看它们是否存在于集合 1 中。（正如我们之前对集合 1 所做的那样）。

完成上述两个集合后，所有非重叠元素将最终被打印出来。

为了找出重叠元素，我们编写了一个名为 non_over 的函数

上述函数负责打印集合 1 和集合 2 的所有非重叠元素。

让我们讨论时间和空间复杂度

时间复杂度：如果我们忽略获取输入所花费的时间。

对于 s1 中的每个元素，我们都在 s2 中搜索每个元素，因此花费的时间是 n1*n2，并且我们执行两次，所以是 2*n1*n2。

我们将其视为 n1*n2。

如果我们将 n1=n2=n 考虑在内，那么时间复杂度是：O(n*2)

空间复杂度：我们没有在这里使用空间，所以空间复杂度保持不变。即 O(1)。

由于时间复杂度是 O(N*2)，我们需要优化代码，

所以，让我们讨论另一种方法

在这种方法中，我们将使用哈希表来存储两个集合的值。

由于映射将两个值存储为键值对，我们可以轻松维护两个集合中每个元素的计数。

即，如果一个元素已经存在于映射中，我们就增加它的计数。否则，我们将添加该元素并将计数设置为 1。

我们将在获取输入时将元素推入映射中，因此所有值都将在获取输入时推入映射中。

为了找出两个集合的非重叠元素，这些元素就是计数值为 1 的元素。

即，任何计数为 1 的元素都被视为非重叠元素。

因此，我们需要部署一个代码，在获取输入时将值插入到映射中，并打印两个集合的非重叠元素。

代码

输出

解释

与之前的代码唯一的区别是这里使用了映射。

我们已将值插入到名为 mp 的映射中。

我们是如何插入的？

使用 mp[x]++，值将被插入到映射中；如果值不存在，将插入一个新值，并且计数器将递增。

现在，我们需要打印映射中计数值为 1 的值，因为只有当计数为 1 时，它才被认为是非重叠元素。

上面是打印非重叠元素的函数。

即，我们检查它。如果第二个是 1，那么我们将打印这些值。否则，我们忽略该元素。

所以，这就是我们将打印两个集合的非重叠元素的方式。

让我们讨论一下代码的时间和空间复杂度

时间复杂度

如果我们忽略获取输入所花费的时间，我们需要时间来打印两个集合的非重叠元素。

它所花费的时间是映射的大小，映射的最大大小可以是 n1+n2，因此在最坏情况下，时间复杂度是 O(n1+n2)。

空间复杂度

此代码所需的空间是一个映射。我们需要一个映射来存储两个集合的元素，因此集合 1 的大小是 n1，集合 2 的大小是 n2，因此总空间是 O(n1+n2)。

时间复杂度： O(n1+n2)

空间复杂度： O(n1+n2)

从以前的方法中，我们可以看到我们已经将时间复杂度从 O(N1*N2) 降低到 O(N1+N2)

空间复杂度从 O(1) 变为 O(N1+N2)