Delete duplicates from array C++

Question

I am trying to create a simple program which calls on 2 functions.
The first function takes a partially filled array, loops through it and deletes any duplicate values. When a value is deleted from the array, the remaining numbers are moved backwards to fill the gap i.e. when the function is finished, all null values of the array will be together at the end.

The second function prints the updated array.

My current code is below. At present when I run my code, the console shows:
2 6 0 -858993460 -858993460 -858993460 -858993460 -858993460 -858993460 -858993460.
It should be showing:
1 2 5 6

Also, I am not sure how to move the remaining elements of the array backwards so that the null values will be together at the end.

#include <iostream>

using namespace std;

void deleteRepeats(int *arr, int arraySize, int& posUsed);
void printArray(int *arr, int arraySize);

int main()
{
    int arr[10] = { 1, 2, 2, 5, 6, 1};
    int posUsed = 6;
    int arraySize = 10;


    deleteRepeats(arr, arraySize, posUsed);
    printArray(arr, arraySize);

    return 0;
}

void deleteRepeats(int *arr, int arraySize, int& posUsed)
{
    for (int i = 0; i < arraySize; i++)
    {
        for (int j = i; j < arraySize; j++)
        {
            if (arr[i] == arr[j])
            {
                for (int k = j; k < arraySize; k++)
                {
                    arr[k] = arr[k + 1];

                }
                posUsed--;
            
            }
            else
                j++;
        }
    }
}

void printArray(int *arr, int arraySize)
{
    for (int i = 0; i < arraySize; i++)
    {
        cout << arr[i] << "  ";
    }
}

Answer 1

I would let the std containers to what you like to do.

• Sort the vector
• Use erase and unique to delete duplicates.

Here is the code

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

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

int main() {
    std::vector<int> arr{1, 2, 2, 5, 6, 1};    
    print(arr);

    std::sort( arr.begin(), arr.end() );
    arr.erase( std::unique( arr.begin(), arr.end() ), arr.end() );

    print(arr);
}

Ps. Using int *arr, int arraySize is not very C++ like. Please always try to use a proper container (which almost always will be std::vector).

EDIT: I changed my answer a bit, because I found this speed comparison (and actuallty the whole question answered). What's the most efficient way to erase duplicates and sort a vector?

Answer 2

It might be easier to imagine the algorithm having separate input and output arrays. Then, in pseudo-code:

for i = 0 to input_array_size-1
    Is input[i] equal to input[j] for any j between 0 and i-1?
    Yes - do nothing
    No - copy input[i] to output

To implement this with shared input and output, you need to have two array sizes, input_array_size and output_array_size. Then, the pseudo-code becomes

output_array_size = 0
for i = 0 to input_array_size-1
    Is array[i] equal to array[j] for any j between 0 and output_array_size-1?
    Yes - do nothing
    No:
        copy array[i] to array[output_array_size]
        Increase output_array_size

Note: it writes output where the input once was, so the check for duplicates should look at all elements that were output. For example, if your array is 1, 2, 1, 3, 5, 6, 3, then for the last 3 the accumulated output is 1, 2, 3, 5, 6, and the code should compare all these with the current element.

---

To simplify debugging, where it says "do nothing", you can set current element to -1. This way, if you print your array during execution (for debugging), it will be clearer which elements were removed.

Answer 3

Given your assignment constraints (more C-like, than idiomatic C++), you can rewrite your function like this, to make it work:

void deleteRepeats(int *arr, int arraySize, int& posUsed)
{
    for (int i = 0; i < posUsed; ++i)
    {
        int duplicates = 0;
        int j = i + 1;
        // find the first duplicate, if exists
        for ( ; j < posUsed; ++j)
        {
            if ( arr[i] == arr[j] ) {
                ++duplicates;
                break;
            }
        }
        // overwrite the duplicated values moving the rest of the elements...
        for (int k = j + 1; k < posUsed; ++k)
        {
            if (arr[i] != arr[k])
            {
                arr[j] = arr[k];
                ++j;
            }
            // ...but skip other duplicates
            else
            {
                ++duplicates;    
            }
        }
        posUsed -= duplicates;
    }
    // clean up (could be limited to the duplicates only)
    for (int i = posUsed; i < arraySize; ++i)
        arr[i] = 0;
}

Answer 4

there are only two changes made as you can see

1: you were traversing the whole array as you have declared a posUsed=6 variable which is because there are only 6 elements so in in loops you need to traverse in array upto posUsed index like i<posUsed j<posUsed k<posUsed

2: the second changes is in j loop j=i+1 because you don't need to compare the element of any index with element of the same index you have to compare it with elements after that index. if you compare it with same element it will be same and the program will delete that same element which results in ERROR.

onw more thing is that we don't traverse after posUsed index because after that the array is already empty/zero or null whatever you call it

and if you want to display just the non duplicated elements and not the zero's at the end of the array just add if(arr[i]==0) return; in the printArray function loop before cout statement

void deleteRepeats(int *arr, int arraySize, int& posUsed)
{
{
    for (int i = 0; i < posUsed; i++)
    {
        for (int j = i+1; j < posUsed; j++)
        {
            if (arr[i] == arr[j])
            {
                for (int k = j; k < posUsed; k++)
                {
                    arr[k] = arr[k + 1];
                    
                }
            }
        
        }
    }
}
}

Answer 5

using two pointers
and if the array sorted

    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int i = 0;

        for(int j = 1; j < nums.size(); j++)
            if(nums[j] != nums[i])  nums[++i] = nums[j];

        // return new array length
        return i + 1;
    }

//input: [1, 1, 2, 1] (arr1)
//output: 2 (returned length)
// print unique element
for(int i = 0; i < output; i++) cout << arr1[i] << '\n';
// [1, 2]

time complexity: O(N/2) -> O(N)
space complexity: O(1)

Answer 6

Removing duplicate elements from an unsorted array by O(n^2) complexity.

    for (i = 1; i < vec.size(); i++)
    {
        for (j = 0; j < i; j++)
        {
            if (vec[i] == vec[j])
            {
                vec[i] = -1; //Every duplicate element will replace by -1
            }
        }
    }

   for (i = 0; i < vec.size(); i++)
    {
        if (vec[i] != -1)
        {
            copy.push_back(vec[i]);

     /*if you are using an array then store this value into a new array.
       first, declare a new array. The new array size will be equal to the 
       previous array. Like this :
       int newArr[sizeOfPreviousArrary];
       int j = 0;
       newArr[j] = arr[i]; 
       j++;
     */

        }
    }

Answer 7

Use map or set for deleting duplicates

void removeDuplicates(int arr[], int n)
{
  
    int i;
  
    // Initialise a set
    // to store the array values
    set<int> s;
  
    // Insert the array elements
    // into the set
    for (i = 0; i < n; i++) {
  
        // insert into set
        s.insert(arr[i]);
    }
  
    set<int>::iterator it;
  
    // Print the array with duplicates removed
    cout << "\nAfter removing duplicates:\n";
    for (it = s.begin(); it != s.end(); ++it)
        cout << *it << ", ";
    cout << '\n';
}

Answer 8

#include <iostream>

using namespace std;

void removedup(int *arr, int &s)
{
    for (int i =0; i<s-1; i++)
    {
        for (int j=i+1; j<s; j++)
        {
            if (arr[i]==arr[j])
            {
                for (int k=j; k<s-1; k++)
                {
                    arr[k] = arr[k+1];
                }
                s--;
                j--;
            }
        }
    }
    for (int i=0; i<s; i++)
    {
        cout << arr [i] <<" ";
    }
    cout << endl ;
}

int main() {
    int n;
    cout << "enter the size of array" << endl;
    cin >> n;
    int *arr = new int[n];
    for (int i=0; i<n; i++)
    {
        cin >> arr [i];
    }
    for (int i=0; i<n; i++)
    {
        cout << arr[i] <<" ";
    }
    cout << endl;
    removedup(arr,n);
    return 0;
}

Answer 9

Removing duplicate elements from an sorted array by O(n) complexity.

for (i = 0; i < n; i++)
{
    if (arr[i] != arr[i+1]){
            vec.push_back(arr[i]);
        
        /*if you are using an array then store this value into a new array.
        first, declare a new array. The new array size will be equal to the 
        previous array. Like this :
            int newArr[sizeOfPreviousArrary];
            int j = 0;
            newArr[j] = arr[i]; 
            j++;
        */
    }
}