1

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
11
  • 3
    Use std::unordered_map<int, int>? Commented May 1, 2022 at 14:14
  • Use a map to calculate the occurrences of these array elements. Commented May 1, 2022 at 14:26
  • map is very slow, I need something faster Commented May 1, 2022 at 14:30
  • If array elements are in a range 0 <= x <=10^5, you can create an array and update there index values to calculate occurrences of these array elements. Commented May 1, 2022 at 14:34
  • 3
    Sort the array. After that, counting duplicates is trivial. Commented May 1, 2022 at 14:51

2 Answers 2

1

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
Sign up to request clarification or add additional context in comments.

1 Comment

This doesn't really address the question. O(whatever) is about how the speed scales when the problem size is increased. It doesn't tell you anything about which approach is faster for a particular set of data. For small data sets, the overhead of a map (in whatever form) can kill performance.
0
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;
}

1 Comment

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.