C Duplicates in array

Question

So lets say i have an array of ints (max being its maximum size)

array = { 1, 7, 22, 3, 7, ... }

and i need to find a way to count the duplicates of each element in the previous array into another array like this one

duplicates = { { 1, 2 times }, { 7, 3 times } ...}

i know the syntax is wrong i just wanted to exemplify my goal (hope i expressed myself well enough) .. i have been thinking and i cant think of a way to do this (maybe it's simple but im kinda new at this) so i decided to post here for some guidance.

Thanks in advance

You are using C not C++? It would much easier to write this in C++.. — Matthias
– Matthias, Commented Apr 24, 2016 at 19:20
i'm having trouble even starting.. like what should i do? i though about making like an auxiliar bidimensional array only with UNIQUE ints from the inicial array, and the count of duplicates it has (initialized at 0) and then for each one see how many times it exists on the original array.. what do you think? i'm thinking this isnt the easiest nor optimal array thats why i chose to ask here — jamez
– jamez, Commented Apr 24, 2016 at 19:26
You could sort the array so the duplicates will be one after the other. — user6214276
– user6214276, Commented Apr 24, 2016 at 19:27
If you sort it first, the algorithm will be O(n*log(n)) (i.e., the performance of the sorting algorithm). Once the array is sorted, producing the array of duplicates is O(n). For the duplicates array, you can define a structure containing two fields, the number itself and the number of occurrences in the original array. You can malloc that array to have the same number of elements as the original array, which is the most you would need. — Andy Schweig
– Andy Schweig, Commented Apr 24, 2016 at 19:32

gsamaras · Accepted Answer · 2016-05-11 18:16:06Z

4

You could sort the array, maybe with an algorithm like qsort and then with a for or a while loop you can count how many times each element appear into the array since the duplicates will be one after another.

If you're under mac/linux type in the terminal man 3 qsort to see how it should be used.

edited May 11, 2016 at 18:16

gsamaras

73.7k50 gold badges210 silver badges330 bronze badges

answered Apr 24, 2016 at 19:24

user6214276

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

Comments

Matthias · Accepted Answer · 2016-04-24 19:32:24Z

0

If memory wasting does not cause any trouble in your case:

Define a struct

struct DuplicationInfo{
   int number;
   int times;
}

Then you can do a loop as follow

DuplicationInfo[max] duplicates;
// Initialze the array
for(int i=0; i < max; i++)
{
    duplicates[i].times= 0;
    duplicates[i].number = -1; // Any invalid number which you know is not in your array
}

for(int i = 0; i < max; i++){
   // Look if the number is still in our duplicates list
   for(int j=0; j<max;j++){
       if(duplicates[j].number == array[i])
       {
           duplicates[j].times++;
           break;
       }
       else if(duplicates[j].number == -1)
       {
           duplicates[j].times= 1;
           duplicates[j].number = array[i];
           break;
       }
   }
}

answered Apr 24, 2016 at 19:32

Matthias

9281 gold badge7 silver badges22 bronze badges

4 Comments

AnatolyS Over a year ago

Let's compile this example with max = 2^32 ;)

Matthias Over a year ago

I know. As I said its only suitable for not that huge arrays.

AnatolyS Over a year ago

I see, your historgam method is suitable only for not wide ranges, but the author have -MAX_INT to +MAX_INT.

Matthias Over a year ago

@AnatolyS then you should add a new boolean member in the struct.

ninazzo · Accepted Answer · 2016-04-26 12:35:30Z

0

You could either sort the array in order to have the duplicates of a number just after the number and count them with a wile or you could use a structure with a number and frequency field. Each time you have to insert a new number into the array, if it is already into the array you just increase by one the frequency field.

answered Apr 26, 2016 at 12:35

ninazzo

6672 gold badges7 silver badges19 bronze badges

Collectives™ on Stack Overflow

C Duplicates in array

3 Answers 3

Comments

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related