How to count duplicate elements in array C ?-CodePudding

I have an array of numbers. I need to find out what numbers are repeated and count the number of repetitions.

I'm thinking of doing this through 2 arrays:

In the first, I will write the number and in the second the number of repetitions of the element. But for this, each number will have to be constantly compared with the first array of numbers.

Do you have any ideas on how to make a faster algorithm?

Examples:

Array of numbers:

1 9 7 8 9 6 9 8 7 1

Two arrays that will come out as a result (if you know how to do it with one array, it will be cool):

1 array:

1 9 7 8 6

2 array:

2 3 2 2 1

CodePudding user response：

All Unordered_set operations are O(1) and O(n) in worse case, but usually remain constant (https://www.geeksforgeeks.org/unordered_set-in-cpp-stl/). In your case you are iterating twice your array, so it would be O(n2). In this case you iterate your array once O(n) and use O(1) set operations, so it would be a faster solution:

#include <iostream>
#include <bits/stdc  .h>

using namespace std;

int main()
{

    int arr[10] = {1, 9, 7, 8, 9, 6, 9, 8, 7, 1};
    unordered_set<int> numbersSet;
    unordered_set<int> duplicateSet;
    int duplicatesCount = 0;

    for (size_t i = 0; i < 10; i  )
    {
        int number = arr[i];
        numbersSet.insert(number);
        if (numbersSet.find(number) != numbersSet.end())
        {
            duplicatesCount  ;
            duplicateSet.insert(number);
        }
    }

    cout << "\nAll elements duplicated : ";
    unordered_set<int>::iterator itr;
    for (itr = duplicateSet.begin(); itr != duplicateSet.end(); itr  )
        cout << (*itr) << endl;

    return 0;
}

All elements duplicated : 6
8
7
9
1

CodePudding user response：

int main()
{
    const int SIZE = 10;
    int arr[SIZE] = {1, 9, 7, 8, 9, 6, 9, 8, 7, 1};
    int find[SIZE] = {0};
    int repeat[SIZE] = {0};
    int temp;
    for (int i = 0; i < SIZE; i  )
    {
        temp = arr[i];
        for (int j = 0; j < SIZE; j  )
        {
            if (i == j)
                continue;
            else{
                if (temp == arr[j])
                {
                    find[i] = temp;
                    repeat[j]  ;
                }   
            }
        }       
    }
    for (int i = 0; i < SIZE; i  )
        cout << arr[i] << ' ';
    cout << endl;
    for (int i = 0; i < SIZE; i  )
        cout << find[i] << ' ';
    cout << endl;
    for (int i = 0; i < SIZE; i  )
        cout << repeat[i]   1 << ' ';
    system("pause");
    return 0;
}