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] << "  ";
    }
}

arr only has room for 6 elements, but you set arraySize = 10. You can change to int arr[10] = { 1, 2, 2, 5, 6, 1 }; — 001
– 001, Commented Oct 10, 2018 at 13:16
Would there be a possibility to use std::vector or std::array? — Micha Wiedenmann
– Micha Wiedenmann, Commented Oct 10, 2018 at 13:16
Thanks @JohnnyMopp I have corrected this. Although I have the same problem with console showing no output. Micha, my lecturer does not want us to use vectors, as we have not covered them yet — Craig
– Craig, Commented Oct 10, 2018 at 13:21
Also, arr[k] = arr[k + 1]; will read past the end of the array when k = arraySize - 1. — 001
– 001, Commented Oct 10, 2018 at 13:21
In your for loops you need to use posUsed and not arraySize. — 001
– 001, Commented Oct 10, 2018 at 13:39

schorsch312 · Accepted Answer · 2024-04-15 08:26:45Z

4

I would let the std containers do 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?

edited Apr 15, 2024 at 8:26

answered Oct 10, 2018 at 14:03

schorsch312

5,7745 gold badges35 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

001 Over a year ago

OP states in comments: my lecturer does not want us to use vectors

pptaszni Over a year ago

OP cannot use standard library algorithms for that assignment. Also, in your solution the result array will be sorted, which might not be desired. Also, you do not need to use for_each to construct a set from vector.

schorsch312 Over a year ago

@Ptaq666 good point. I replaced for_each. This enhanced the const correctness.

schorsch312 Over a year ago

@JohnnyMopp I have not read this comment before posting my answer. Nevertheless, teaching C++ without proper container is ihmo not the right way to do it. There is no point in still using pointers and sizes if a std::vector can be used. C++ should be taught as shown in A Tour of C++ by Stroustrup.

PaulMcKenzie Over a year ago

Where did the OP state that the algorithm functions couldn't be used? I see that they cannot use vector, but vector is not an algorithm function.

|

Bob__ · Accepted Answer · 2018-10-10 14:55:25Z

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;
}

anatolyg · Accepted Answer · 2018-10-10 14:38:08Z

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.

user13703720 · Accepted Answer · 2020-11-16 13:48:43Z

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];
                    
                }
            }
        
        }
    }
}
}

Ahmed Eid · Accepted Answer · 2020-05-31 19:10:10Z

0

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)

edited May 31, 2020 at 19:10

answered May 31, 2020 at 19:04

Ahmed Eid

3323 silver badges9 bronze badges

Comments

mr. conqueror · Accepted Answer · 2021-10-23 14:40:41Z

0

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++;
     */

        }
    }

edited Oct 23, 2021 at 14:40

answered Sep 29, 2021 at 5:49

mr. conqueror

11 bronze badge

Comments

Suraj Rao · Accepted Answer · 2022-05-30 05:52:59Z

0

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';
}

edited May 30, 2022 at 5:52

Suraj Rao

29.7k11 gold badges96 silver badges104 bronze badges

answered May 30, 2022 at 5:44

TEJAS LUTE

1

1 Comment

UpAndAdam Over a year ago

why would you use a map to delete duplicates?

UpAndAdam · Accepted Answer · 2023-07-19 16:20:08Z

0

#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;
}

edited Jul 19, 2023 at 16:20

UpAndAdam

5,5075 gold badges33 silver badges49 bronze badges

answered Jul 15, 2023 at 15:18

Himanshu

1

1 Comment

Himanshu Over a year ago

This C++ code is removing the duplicate elements of the entered array and giving the array with distinct elements only as output regardless whatever the size of the array and whatever the number of duplicate elements in the entered array.

UpAndAdam · Accepted Answer · 2024-04-03 21:36:08Z

0

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. Note the array must be declared outside of the loop or it will be destroyed. 
        Like this :
            int newArr[sizeOfPreviousArrary];
            int j = 0;
            newArr[j] = arr[i]; 
            j++;
        */
    }
}

edited Apr 3, 2024 at 21:36

UpAndAdam

5,5075 gold badges33 silver badges49 bronze badges

answered Oct 23, 2021 at 14:50

mr. conqueror

11 bronze badge

1 Comment

UpAndAdam Over a year ago

this is horrible. you aren't removing items, you are adding items to a new container and you are assuming they are sorted which they are not.

Collectives™ on Stack Overflow

Delete duplicates from array C++

9 Answers 9

8 Comments

Comments

Comments

Comments

Comments

Comments

1 Comment

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

9 Answers 9

8 Comments

Comments

Comments

Comments

Comments

Comments

1 Comment

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related