Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Removing Duplicates from an Array using C [duplicate]

Tags:

c

algorithm

I want small clarification in array concept in C. I have array:

int a[11]={1,2,3,4,5,11,11,11,11,16,16};

I want result like this:

{1,2,3,4,5,11,16}

Means I want remove duplicates. How is it possible?

like image 726
user1087515 Avatar asked Dec 22 '22 01:12

user1087515


2 Answers

You can't readily resize arrays in C - at least, not arrays as you've declared that one. Clearly, if the data is in sorted order, it is straight-forward to copy the data to the front of the allocated array and treat it as if it was of the correct smaller size (and it is a linear O(n) algorithm). If the data is not sorted, it gets messier; the trivial algorithm is quadratic, so maybe a sort (O(N lg N)) followed by the linear algorithm is best for that.

You can use dynamically allocated memory to manage arrays. That may be beyond where you've reached in your studies, though.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

static int intcmp(const void *pa, const void *pb)
{
    int a = *(int *)pa;
    int b = *(int *)pb;
    if (a > b)
        return +1;
    else if (a < b)
        return -1;
    else
        return 0;
}

static int compact(int *array, int size)
{
    int i;
    int last = 0;
    assert(size >= 0);
    if (size <= 0)
        return size;
    for (i = 1; i < size; i++)
    {
        if (array[i] != array[last])
            array[++last] = array[i];
    }
    return(last + 1);
}

static void print(int *array, int size, const char *tag, const char *name)
{
   int i;
   printf("%s\n", tag);
   for (i = 0; i < size; i++)
       printf("%s[%d] = %d\n", name, i, array[i]);
}

int main(void)
{
   int a[11] = {1,2,3,4,5,11,11,11,11,16,16};
   int a_size = sizeof(a) / sizeof(a[0]);

   print(a, a_size, "Before", "a");
   a_size = compact(a, a_size);
   print(a, a_size, "After", "a");

   int b[11] = {11,1,11,3,16,2,5,11,4,11,16};
   int b_size = sizeof(b) / sizeof(b[0]);

   print(b, b_size, "Before", "b");
   qsort(b, b_size, sizeof(b[0]), intcmp);
   print(b, b_size, "Sorted", "b");
   b_size = compact(b, b_size);
   print(b, b_size, "After", "b");

   return 0;
}
like image 83
Jonathan Leffler Avatar answered Jan 01 '23 10:01

Jonathan Leffler


#define arraysize(x)  (sizeof(x) / sizeof(x[0])) // put this before main

int main() {
    bool duplicate = false; 
    int a[11] = {1,2,3,4,5,11,11,11,11,16,16}; // doesnt have to be sorted
    int b[11];
    int index = 0;

    for(int i = 0; i < arraysize(a); i++) { // looping through the main array
        for(int j = 0; j < index; j++) { // looping through the target array where we know we have data. if we haven't found anything yet, this wont loop
            if(a[i] == b[j]) { // if the target array contains the object, no need to continue further. 
                duplicate = true;
                break; // break from this loop
            }
        }
        if(!duplicate) { // if our value wasn't found in 'b' we will add this non-dublicate at index
           b[index] = a[i];
           index++;
        }
        duplicate = false; // restart
    }
    // optional 
    int c[index]; // index will be the number of objects we have in b

    for(int k = 0; k < index; k++) {
        c[k] = b[k];
    }
}

If you really have to you can create a new array where that is the correct size and copy this into it.

As you can see, C is a very basic (but powerful) language and if you can, use a vector to but your objects in instead (c++'s std::vector perhaps) which can easily increase with your needs.

But as long as you only use small numbers of integers you shouldn't loose to much. If you have big numbers of data, you can always allocate the array on the heap with "malloc()" and pick a smaller size (maybe half the size of the original source array) that you then can increase (using realloc()) as you add more objects to it. There is some downsides reallocating the memory all the time as well but it is a decision you have to make - fast but allocation more data then you need? or slower and having the exact number of elements you need allocated (which you really cant control since malloc() might allocate more data then you need in some cases).

like image 26
chikuba Avatar answered Jan 01 '23 08:01

chikuba