获取集合中重复元素的个数

Question

所以集合不允许重复，但是有没有一种方法，或者另一种数据结构，可以让我得到重复元素的数量，即使它们已经被删除了?无论如何，让我更好地解释一下。

假设我输入的是:

[1, 2, 2, 3, 2, 5, 3]

如果我把它放在一个集合中，它会像这样结束:

[1, 2, 3, 5]

这是我想要的，但是我怎么知道在它们被移除之前有三个2s呢?这不是和那些有"桶"的数据结构有关吗?还是什么?

基本上我希望输出是这样的:

[1, 2, 3, 5]
|  |  |  |
[1, 3, 2, 1]

底部数组为顶部数组中每个元素的重复个数。

Answer 1

您可以使用std::map来计算项目的频率。

例如:

int arr[] = {1, 2, 2, 3, 2, 5, 3};
std::map<int, int> count;
for (int i = 0; i < 7; i++) {
count[arr[i]]++;
}
for (auto& [element, frequency] : count) {
std::cout << element << " : " << frequency << endl;
}

输出会像这样:

1 : 1
2 : 3
3 : 2
5 : 1

Answer 2

您自己给出了答案:保持计数与唯一元素的对应就足够了。因此，紧凑的数据结构是唯一元素的列表与相同顺序的计数列表配对。

现在，如何获得它取决于您计划如何删除重复项和所需的访问类型。一种方法是对初始列表进行排序，在计数和填充计数列表的同时清除重复项。另一种方法是使用将列表元素作为键的映射，并将它们与计数相关联。是保留地图还是填写新的列表由你选择。

Answer 3

c++中一个集合中重复元素的个数可以用size()函数减去该集合中唯一元素的个数，而唯一元素的个数可以用unique()函数求出。

#include <iostream>
#include <set>
#include <algorithm>
int main()
{
std::set<int> mySet;
mySet.insert(1);
mySet.insert(2);
mySet.insert(2);
mySet.insert(3);
mySet.insert(3);
mySet.insert(3);
int numDuplicates = 0;
int lastElement = -1;
for (int element : mySet) {
if (element == lastElement) {
numDuplicates++;
}
lastElement = element;
}
std::cout << numDuplicates << std::endl;
return 0;
}