Is there a way to find duplicates effectively?

Question

I'm trying to find duplicates even though they have been put in by user input. I've tried a few methods, for loop to do the checks but that doesnt work. Anyone got any idea how I might be able to do this effectively?

#include <iostream>
#include <algorithm>

int main()
{
    int size, * array; 
    std::cout << "Indtast arrayet's stoerrelse." << std::endl;
    std::cin >> size; // optager input til størrelse af arrayet fra brugeren
    array = new int[size]; // dynamisk allokeret array

    while (size >= 100) { // while loop til at tjekke om arrayets størrelse er for stort
        std::cout << "Forkert input af array." << std::endl;
        break;
    }

    while (size <= 100) { // while loop til når arrayet er af rigtig størrelse

        float sum = 0;
        float gns = 0;

        std::cout << "Tast op til " << size << " vaerdier ind." << std::endl; 

        for (int i = 0; i < size; i++) { // for loop til at optage input til hver element i arrayen
            std::cout << "Indtast vaerdi for array-nr: " << i << std::endl;
            std::cin >> array[i]; // optager input til hvert element

            sum += array[i]; // finder summen af elementerne i arrayet
        }
        std::cout << "Min-vaerdi er: " << *std::min_element(array, array + size) << std::endl;
        std::cout << "Max-vaerdi er: " << *std::max_element(array, array + size) << std::endl;
        std::cout << "Summen er: " << sum << std::endl;
        gns = sum / size; // udregner gennemsnittet 
        std::cout << "Gennemsnittet er: " << gns << std::endl;


        return 0;
    }
}

Or put the input in a `set` and all the duplicates will be gone automatically. — Ted Lyngmo, Sep 30 '22 at 13:04
`while(size <= 100) { ...; return 0; }` ... that looks off. It looks like `while (size <= 100) ` should have been `else` and `while (size >= 100)` should have been `if (size >= 100)` — Ted Lyngmo, Sep 30 '22 at 13:06
*Is there a way to find duplicates effectively?* -- `std::sort`, and then if you want to find where they are, [std::adjacent_find](https://en.cppreference.com/w/cpp/algorithm/adjacent_find). — PaulMcKenzie, Sep 30 '22 at 13:14
`I'm trying to find duplicates` is not full description of problem which this code suppose to solve (everything else is just complains it doesn't work). Also string literals and comments are not in English so it is hard decipher what this suppose to do. Please provide better description and example of input and output (unit test are best in that). Please read [ask]. — Marek R, Sep 30 '22 at 13:24
That code makes no attempt to find duplicates. Why is it relevant to your question? — molbdnilo, Sep 30 '22 at 13:34
_"I'm trying to find duplicates..."_ - Since there's no effort made to find them in your current code, what will you do once you find a duplicate? Just remove it? — Ted Lyngmo, Sep 30 '22 at 13:44
I tried using for loops to find the duplicates, I since removed those lines of code. a for loop for i and j+1 — VIGGO420, Sep 30 '22 at 14:09
@VIGGO420 Ok ... and... what will you do once you find a duplicate? Remove/exclude it from the mean value calculation? — Ted Lyngmo, Sep 30 '22 at 14:10
Please consider using https://codereview.stackexchange.com as this is not safe nor modern C++ and the community will be able to help you improve your code. Generally, for example, you should not be using "new". Read up on the STL and especially std::set. Also there is a mixture of integral and floating point data types, which looks wrong. — T33C, Sep 30 '22 at 14:19
Ok, so it should still be included in the mean value calculation? Oh, well, then do what's suggested. `std::sort` the array and then `std::adjacent_find` the duplicates. Don't use `new[]`/`delete[]` though. Use a `std::vector array(size);` instead. — Ted Lyngmo, Sep 30 '22 at 14:19

score 0 · Answer 1 · answered Sep 30 '22 at 15:38

Here is a modern (C++20) approach using ranges. As suggested in the comments, you should sort your vector and then use adjacent_if. It is always recommended to use the algorithms from the standard library than to try to re-implement common stuff like this yourself using basic procedural tools like for and while loops.

This approach would work with an array as well, but I suggest using an std::vector.

#include <vector>
#include <algorithm>
#include <iostream>

void print(std::vector<int> const& v){
    // print the vector
    for (auto const& i: v){
        std::cout << i << ", ";
    }
    std::cout<<"\n";
};

int main()
{
    std::vector<int> v{1, 2, 1, 1, 3, 3, 3, 4, 5, 4};

    std::cout << "Input vector = \t\t";
    print(v);

    // sort the vector
    std::ranges::sort(v);

    std::cout << "Sorted vector = \t";
    print(v);

    // find duplicates and print them
    auto it = std::ranges::adjacent_find(v);
    while (it != v.end()){
        std::cout 
            << "Duplicates start at v[" 
            << std::distance(v.begin(), it)
            << "] = "
            << *it
            << "\n";
        it = std::ranges::adjacent_find(it, v.end(), std::ranges::not_equal_to());
        it = std::ranges::adjacent_find(it, v.end());
    }
    for (; it != v.end(); ++it){
        std::cout << *it << std::endl;
    }

    // remove duplicates    
    auto ret = std::ranges::unique(v);
    v.erase(ret.begin(), ret.end());

    std::cout << "No duplicates = \t";
    print(v);
    

    return 0;
}

Output:

Input vector =      1, 2, 1, 1, 3, 3, 3, 4, 5, 4, 
Sorted vector =     1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 
Duplicates start at v[0] = 1
Duplicates start at v[4] = 3
Duplicates start at v[7] = 4
No duplicates =     1, 2, 3, 4, 5,

Try it on compiler explorer: https://godbolt.org/z/YP3zb7PYf

In case you want to know the indices of the duplicates in your unsorted input array: https://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes — joergbrech, Sep 30 '22 at 15:41

Is there a way to find duplicates effectively?

1 Answers1