具有不同元素的最小子集数量

我们将为具有不同元素的最小子集数提供一个数组或向量

在问题中。我们需要找出要完成的最小子集数，以便任何子集中都没有重复或重复的元素。

让我们举个例子

如果向量是 vec = [1,2,3,3]

现在，我们需要划分上述向量，使得每个子集中不应有重复元素。

可能的划分方式是

{1,2,3},{3}

或

{3,1},{2,3}

或

{2,3},{1,3}

通过划分成任意两个子集，我们使得每个子集中都有不同的元素，我们的要求是需要多少个子集才能满足条件。

在上述情况下我们完成了两个子集，所以答案是 2。

现在，我们需要编写代码来找出所需的最小子集数

代码

输出

说明

逻辑

我们如何找到可能的子集数量？

如果我们从数学角度思考，可能的子集数量等于数字重复的次数。

就像在第一个例子中，我们必须取一个向量作为 [1,2,3,3]

在这里，1 和 2 只出现一次，但 3 出现了 2 次，因此可能的子集数量也是 2。

因此，可能的子集数量等于重复次数最多的元素。

所以，我们需要确定整个向量中重复次数最多的元素。

现在让我们讨论代码

首先，我们需要输入向量大小和向量元素

上面的代码行将把向量大小作为输入，然后把向量元素作为输入。

现在，我们需要找出重复元素的最大频率以及一个元素在整个向量中重复的次数。

因此，对于每个元素，我们需要找出频率。为了找出向量中每个元素的频率，我们搜索整个向量，除了相同索引的元素，并找出每个元素的频率。

代码的这一部分将确定每个向量元素的频率。在寻找向量频率的同时，我们会将频率存储在一个名为 m 的变量中，我们知道我们应该找到整个数组的最大频率，所以它由 ans=max(ans,m) 处理，这将有助于存储最大频率。

最后，在找到每个元素的频率后，最大值将存储在 ans 变量中，最后我们将打印它。

在这里，我们需要处理一种情况，即当没有重复元素时；在这种情况下，ans 变量中的值将存储为 1；当 ans 为 1 时，我们将打印“无需划分向量元素，所有元素都是不同的”。

否则，我们将打印区分向量元素所需的子集数量。

代码的上述部分将处理打印，如果存在重复元素，或者不存在重复元素。

现在我们来讨论一下这段代码的时间和空间复杂度

时间复杂度： 如果我们忽略获取输入所花费的时间，那么时间主要消耗在查找向量中每个元素的频率上。

对于向量中的每个元素，我们都必须搜索整个向量，所以花费的时间将是 O(N*2)

空间复杂度

在此代码中，我们没有使用任何空间，因此此代码占用常量空间，即 O(1)。

在前面的方法中，所花费的时间是 O(N*2)，但我们需要降低代码的时间复杂度。

为了降低代码的时间复杂度，我们将使用映射，因为映射可以存储两个变量，一个用于元素，另一个用于元素的计数。

对于上述问题，我们需要每个元素的计数，因此使用映射是一种完美的方法。

所以，让我们使用映射来实现代码。

代码

输出

解释

首先，我们需要从用户那里获取向量大小和向量元素的输入，并将向量的元素推入映射中，其中计数将存储在每个映射元素的第二个变量中。

上述代码行将获取向量大小和向量元素的输入；在获取输入的同时，我们还将值存储在映射中。如果元素不在映射中，将添加一个新元素。元素的频率将增加。

现在，我们需要找到所有映射元素的最大频率，为此，我们需要遍历映射并使用 for 循环来完成。

代码的以上部分将找到任何出现元素的最大频率。

如果频率或答案为 1，则表示所有元素都是不同的，因此无需创建子集。

代码的以上部分将打印所需子集的最小数量。如果不需要创建子集，则条件满足并打印以下语句；否则，将打印 else 下的语句。

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

时间复杂度： 如果我们忽略获取输入所花费的时间，那么我们遍历映射以找到最大计数，映射的最大可能长度为 N，因此时间复杂度将为 O(N)

空间复杂度： 在这里，我们使用映射来存储向量的元素，在最坏的情况下，映射也占用了 N 空间来存储向量的元素，因此空间复杂度为 O(N)。

方法表格表示