Remove duplicates from array and save it to another one

Question

So I have been tasked to make an array without duplicated values from another existing array. So I did it, but I want to know is there some other better way to do that.

Example input/output:

Input: 10, 15, 10, 5, 1, 3

Output: 10, 15, 5, 1, 3

So here is my code.

#include <stdio.h>

int main(void) {
  const int MAX_ARRAY_SIZE = 5;

  int m[MAX_ARRAY_SIZE], p[MAX_ARRAY_SIZE];


  for(int i = 0; i < MAX_ARRAY_SIZE; i++) {
    printf("Enter number: ");
    scanf("%d",&m[i]);
  }
  int k = 0;
  int dup = 0;
  for(int i =0; i < MAX_ARRAY_SIZE; i++) {
    for(int j = i +1; j <MAX_ARRAY_SIZE; j++) {
        if(m[i] == m[j]) {
            dup = 1;
        }
    }
    if(dup != 1) {
      p[k++] = m[i];
    }
    dup = 0;
  }

  printf("The new array without repeated values\n");
  for(int i = 0; i < k; i++) {
    printf("%d\n",p[i]);
  }

  return 0;
}

I'm not sure if this is the right and simple way I do that. I want some suggestions.

Thanks in advance. :)

Answer 1

Early termination

After

        dup = 1;

you should break. There's no need to execute the rest of the loop.

Booleans

Consider using <stdbool.h>, making bool dup = false, later assigning it true, and writing if (!dup).

Complexity

In practical terms, an array of five values poses no computational cost. However, if your prof cares about complexity analysis, the "proper" solution to this would need to complete in linear time (rather than your current quadratic time), using something like a hash-set, with pseudocode:

Set *seen = make_set();
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
    int m;
    scanf(&m);
    if (!contains(seen, m))
        add(seen, m);
}

for (m in seen)
    printf(m);

Answer 2

This Q needs some dedup itself. Remove duplicates... But since this is my third version of the inner loop I take advantage of a fresh start.

This inoffensive assignment int j = i + 1;, originally packed into the for-expression-list, does more than just initialize j for the last i: it makes m[j] illegal/undefined.

The goal (?) is to avoid the dup flag and to "normalize" the loops. I think this rearrangement is worth it:

    int j;
    for (int i = 0; i < ARRAY_SIZE; i++) {
        j = i;
        do
            if (++j == ARRAY_SIZE) {   // already past end?    
                p[k++] = m[i];            // copy this one
                break;                    // and finish
            }
        while (m[i] != m[j]);          // if match, then just finish 
    }

Now everything is at the natural place.

I wrote do statement while (expr); without braces to illustrate the structure. What is a bit hidden is the loop increment if (++j....

---

Instead of a real (sorted) structure one can use the new unique array to search for duplicates. Because of the 0 already in the new array I first copy the first element unconditionally, and then start the loop with the second element.

    int k = 1;
    /* First is always unique */
    printf("m[0] -> p[0]\n");
    p[0] = m[0];
    for (int i = 1; i < ARRAY_SIZE; i++)
        for (int j = 0;; j++) {
            if (j == k) {         
                printf("m[i=%d] -> p[k=%d]\n", i, k);
                p[k++] = m[i];
                break;
            }
            if (p[j] == m[i])
                break;
        }

Still this if (p[j] == m[i]) has to be logically after if (j == k), so the for-loop has to be freestyled a bit.

The printfs illustrate:

Enter number: 6
Enter number: 6
Enter number: 0
Enter number: 0
Enter number: 8
m[0] -> p[0]
m[i=2] -> p[k=1]
m[i=4] -> p[k=2]
The array without repeated values
6
0
8

Side effect: the order is now preserved.

I guess this is a bit tricky because the searching and inserting are so closely connected. The k index must be handled precisely. (the other ones also)

Performance: I don't even know if using the new array up to k is faster than OP searching the rest of the original. It seems to amount to the same at least for some cases.

Problem is the new array is not sorted. Keeping it sorted costs too much if done naively, after every insert.

So one would have to "spread" out first in order to search efficiently. For (random) integers, modulo 10 can create ten different arrays - or buckets. With a 2D b[][] (instead of OP p[] )

b[0] {100}
b[1] {1, 31, 20001}
b[2] {12, 32, 502}
b[3] {}
b[4] {94}
...

Every (sub)array needs the original ARRAY_SIZE for the worst case. But now the array to search for dups is 10 times shorter on average.

---

So you could change the interactive input into a one-million-integers array generator and do some tests.

---

All because of that dup loop flag ;)

Answer 3

A few comments:

• Using printf/scanf is something like thirty years out of date. Use cin and cout instead. They are superior in almost every way -- easier to read, type safe, not prone to stack overflow, etc. etc.

• I am sure this is controversial, since, especially among C/C++ programmers brevity seems more important than clarity, but all those single letter variable names that bear no resemblance to their purpose makes the code way harder to follow. Why not call m "withDups" and p "noDups"? It'd make it a lot clearer what you are doing. Why not call k "noDupsEnd"? I'd go so far as to change the names of i,j too since that is just confusing, but I will grant that this is standard practice in C/C++

• So instead of i,j use a better form of forloop:

    for(int passOne: withDups)
    {
        for(int passTwo: withDups)
          ifpassOne == passTwo)
          {
             dup = true;
             break;
          }
       if(! dup) noDups[noDupsEnd++] = withDups[passOne];
   }
   // Or something like that. My C++ is a bit out of date, but I believe that is correct.
  

The advantage of this being that you are less likely to make dumb mistakes and the code is easier to understand.

• You could further simplify this by making the inner loop search noDups upto notDupsEnd, meaning that it'll make less passes in general.
• Finally, algorithmically, I think truthfully it depends on the actual underlying requirements. If you are dealing with arrays of five elements (or let's say up to 100 elements) then your solution is algorithmically fine. However, the complexity of this is potentially quadratic. This is a brute force approach. If you are going to have larger lists you need better data structures, such as a hash set, or a tree to maintain the values already in nodups. That is obviously rather more complex, but will reduce the performance complexity substantially, potentially to close linear with a good hash table, if you have lots of memory, or at least n.log(n) with a tree structure of some kind.

For example, if you use a simple hash table (forgive, my C++ is a bit rusty) you might do something like this. Here I am using vectors which are more flexible than fixed size arrays.

// Return a vector containing the input vector maintaining order but removing duplicates.
// Neither input or output vector can contain -1
std::vector<int> removeDups(std:vector<int> arr)
{
   // We need a bit more space in our hash table than the original table, so this
   //  multiplier gives us extra space
   const int hashTblMultiplier = 2;
   const int hashTblSize = arr.size() * hasTblMultiplier;
   // Give it a capacity to make sure it doesn't go through qaudratic copies in expansions.
   // If a vector has to auto expand then it must copy all its contents, so if the vector
   /// has too small a capacity it can drop into some nasty performance behaviors.
   const result = new std::vector<int>(size /2);
   // For this simple implementation I assume arr only has positive values. Otherwise the hash
   // table will have to be a bit more complicated.
   auto hashTable = new std:vector<int>(hashTblSize, -1);
   for(int item: arr)
   {
      // Use simple linear probing for hash collision resolution and a simple hash function
      // which assumes the input data is equally distributed.
      int hash = item % hashTblSize;
      while(hashTbl[hash] != item && hashTbl[hash] != -1)
         hash = (hash+1)%hashTblSize;
      if(hashTbl[hash] == -1)
      {
         hasTbl[hash] = item;
         result.push_back(item);
      }
   }
   return result;
}