c++ - Remove duplicates from an unsorted array

Question

I'm trying to create a function to remove duplicates from an unsorted int array. I have a solution that works for more examples, but it's failing with the following input:

#include<iostream>
using namespace std;

int removeDuplicates(int arr[], int n)
{
    int j = 0;

    for (int i=0; i < n; i++){
        for(int j=0;j<=i;j++){

            if(arr[i]==arr[j]){
                 n--;
                for (int k=i; k<n; k++){
                    arr[k]=arr[k+1];
                }
            }
        }
    }

    return n;
}

// Driver code
int main()
{
    int arr[] = {0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    n = removeDuplicates(arr, n);

    for (int i=0; i<n; i++)
        cout << arr[i] << " ";

    return 0;
}

The output for this arr example is 0 0 1 0 0 and should be 0 1.

Do you see where is the problem? Thank you

Answer 1

Consider using std::set<int> to record numbers you've already seen, and using a STL algorithm to perform the removal:

#include<iostream>
#include<algorithm>
#include<functional>
#include<set>

// Driver code
int main()
{
    int arr[] = {0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1};
    std::set<int> duplicates;

    auto it = std::remove_if(std::begin(arr), std::end(arr), [&duplicates](int i) {
        return !duplicates.insert(i).second;
    });
    size_t n = std::distance(std::begin(arr), it);

    for (size_t i = 0; i < n; i++)
        std::cout << arr[i] << " ";

    return 0;
}

The effect of this code is that all duplicates are moved to the end of the array, and the iterator returned by std::remove_if indicates the end of the new list. So iterating between the beginning and that iterator gives you the array without the duplicates.