CODEWITHSUNDEEP
c++
user2502162
user2502162

Reputation:

copy one array to another without duplicates C++

The problem is that, I have an array of 10 integers, having some duplicates. The task is to copy this array to another array of same size, but without duplicate values. That is, read one element from array1, compare it with all the elements in array2, if it's already in array2, just skip it or print that it's already in array2, go to second element of array1, and repeat the process. Now, I've tried this but don't know where's the problem:

#include <iostream>
using namespace std;

int main()
{
    int temp;

    int array1[] = {10,2,5,4,10,5,6,9,8,10};
    int array2[11] = {0};

    for(int i = 1; i <= 10; i++)
    {
            temp = array1[i-1];

            for(int j = 1; j <= 10; j++)
            {
                    if(temp == array2[j])
                    {
                            cout << "Duplicate " << temp << endl;
                            i++;
                            break;
                    }
            }

            array2[i] = array1[i-1];
    }

    for(int k = 1; k <= 10; k++)
            cout << array2[k] << "  " << endl;
system("pause");
}

Upvotes: 0

Views: 4800

Answers (7)

ondrejdee
ondrejdee

Reputation: 466

I can see two main sources of problems in your code: 1) the break statement, as it is, does not solve the problem of differentiating between the case when duplicate is found, and when the element in array1 should be added to array2. 2) There is no counter which would store the number of elements inserted so far into array2, this way they could not be copied to array2 next to each other. The code which fixes both is:

#include <iostream>
using namespace std;

int main()
{

  int array1[] = {10,2,5,4,10,5,6,9,8,10};
  int array2[10];

  int array2_elements_inserted = 0; 

  for(int i = 0; i < 10; i++)
    {
      int temp = array1[i];

      bool isDuplicate = false; 
      for(int j = 0; j < array2_elements_inserted; j++)
        {
          if(temp == array2[j])
            {
              cout << "Duplicate " << temp << endl;
              isDuplicate = true; 
              break;
            }
        }

      if (!isDuplicate)
        {
          array2[array2_elements_inserted] = temp;
          ++array2_elements_inserted; 
        }
    }

    for(int k = 0; k < array2_elements_inserted; k++)
        cout << array2[k] << "  " << endl;
  //  system("pause");
}

Output: 

10  
2  
5  
4  
6  
9  
8

Upvotes: 0

moooeeeep
moooeeeep

Reputation: 32502

First of all, use dynamic containers. Especially have a look at those provide by the standard library, e.g. std::vector. Second, you should use a set data structure to keep track of the elements you have seen before, e.g., std::set.

Then it's just an iteration on the input array and appending new elements to the output array.

Here's an example:

#include <vector>
#include <set>
#include <iostream>

int main() {
    // define and print input data
    std::vector<int> v1 = {10,2,5,4,10,5,6,9,8,10};
    for (int i : v1) 
        std::cout << i << " ";
    std::cout << "\n";
    // this will soon contain the output data
    std::vector<int> v2;
    // a set to keep track of the already seen elements 
    std::set<int> set;
    // iterate the input array using range-based for loop
    for (int i : v1) {
        // check for duplicates
        if (set.find(i) == set.end()) {
            // first occurrence, insert to set, append to output data
            set.insert(i);
            v2.push_back(i);
        }
        else {
            // seen before, do nothing
        }
    }
    // print output data
    for (int i : v2) 
        std::cout << i << " ";
    std::cout << "\n";    
}

The output:

$ g++ test.cc -std=c++11 && ./a.out
10 2 5 4 10 5 6 9 8 10 
10 2 5 4 6 9 8

For reference:

Upvotes: -1

PP.
PP.

Reputation: 10864

You have three approaches:

  • compare each element one by one (O(N^2) performance)
  • sort your reference array and use a binary search to determine if the element exists (O(N*lnN) performance)
  • create a lookup hash (O(1) performance)

Upvotes: 0

Enigma
Enigma

Reputation: 1717

You could use a std::set to ensure uniqueness for you.

http://en.cppreference.com/w/cpp/container/set

Upvotes: 0

IanPudney
IanPudney

Reputation: 6021

In C++, break immediately ends one loop structure, and starts execution immediately after it. Thus, the line array2[i] = array1[i-1]; executes redardless of whether the inner for loop finds a duplicate. One solution is to set a variable indicating that the value is a duplicate:

 int main() {
     int temp;
     bool isDuplicate; //added this line

     int array1[] = {10,2,5,4,10,5,6,9,8,10};
     int array2[11] = {0};

     for(int i = 1; i <= 10; i++)
     {
             temp = array1[i-1];
             isDuplicate=false;//added this line
             for(int j = 1; j <= 10; j++)
             {
                     if(temp == array2[j])
                     {
                             cout << "Duplicate " << temp << endl;
                             i++;
                             isDuplicate=true; //added this line
                             break;
                     }
             }
             if(!isDuplicate) //added this line
             array2[i] = array1[i-1];
     }

     for(int k = 1; k <= 10; k++)
             cout << array2[k] << "  " << endl; system("pause"); }

Alternatively (though many programmers would disagree with this practice) you could use a goto statement instead of a break statement:

int main()
{
    int temp;

    int array1[] = {10,2,5,4,10,5,6,9,8,10};
    int array2[11] = {0};

    for(int i = 1; i <= 10; i++)
    {
            temp = array1[i-1];

            for(int j = 1; j <= 10; j++)
            {
                    if(temp == array2[j])
                    {
                            cout << "Duplicate " << temp << endl;
                            i++;
                            goto duplicate; //added this line
                    }
            }

            array2[i] = array1[i-1];
            //added next line
            duplicate:
    }

    for(int k = 1; k <= 10; k++)
            cout << array2[k] << "  " << endl;
system("pause");
}

Upvotes: 0

Pete Becker
Pete Becker

Reputation: 76245

array1 has 10 elements and array2 has 11, so right away the requirements haven't been met. Presumably, having 11 elements was a workaround for using incorrect index values in the for loops; the index should run from 0 to 9, not from 1 to 10.

When you add an element to the second array, you should only check it value against the elements that have already been added, not against the values in the entire array.

Finally, there's an underspecification. Once you've eliminated duplicates, you have fewer than 10 elements; array2 has 10 elements; what values should the extra elements have?

Upvotes: 3

Enigma
Enigma

Reputation: 1717

std::unique_copy is your friend: http://en.cppreference.com/w/cpp/algorithm/unique_copy

remember to sort the source array first

Upvotes: 1

Related Questions