Karlos
Karlos

Reputation: 357

Get the number of duplicated elements in a set

So a set doesn't allow duplicates, but is there a way, or another data structure, that can allow me to get the number of repeated elements even though they have been removed?. Let me explain myself better anyways.

Lets say I'm giveng this input:

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

If I put it in a set, it will end up like this:

[1, 2, 3, 5]

Which is what I want, but how can I know that there were three 2s before they were removed? Isn't this related to those data structure with "buckets" or something?

Basically I'd like the output to be something like this:

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

With the bottom array being the number of duplicates of each element on the top array.

Upvotes: 1

Views: 824

Answers (3)

Gaurav Siwach
Gaurav Siwach

Reputation: 11

The number of duplicate elements in a set in C++ can be determined by using the size() function and subtracting the number of unique elements in the set, which can be found by using the unique() function.

#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;
}

Upvotes: 1

user1196549
user1196549

Reputation:

You gave the answer yourself: if suffices to keep counts in correspondence to the unique elements. Hence a compact data structure is the list of the unique elements paired with the list of counts in the same order.

Now how this is obtained depends on how you plan to remove the duplicates and the kind of access desired. One way is to sort the initial list, purge the duplicates at the same time that you count them and fill the list of counts. Another way is to use a map with the list elements as keys and associate them with a count. Whether you keep the map or fill new lists is your choice.

Upvotes: 1

J Muzhen
J Muzhen

Reputation: 352

You can use a std::map to count the frequency of the items.

For example:

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;
}

The output would be something like this:

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

Upvotes: 3

Related Questions