c array question

Question

I have an array like this:

int sayilar[10] = {5,6,2,1,4,2,5,5,5,2};

now I want to get a result like: 2 duplicates found, 5= 4 times, 2= 3times.

Couldn't figure how to do that. Here is my code, that's not working right:

#include <stdio.h>

int main()
{
    int sayilar[10]={5,6,2,1,4,2,5,5,5,2};
    int i,j;
    int matris[5][2];

    int ar[5];

    int temp=0;
    int tempX;
    int k=0;

    for(i=0; i<10; i++)
    {
        for(j=i+1; j<10; j++)
        {
            if(sayilar[j]==sayilar[i])
            {
                if(temp==0)
                {
                    matris[k][0] = sayilar[j];
                    matris[k][1] = 1;
                    temp=1;
                } else
                {
                    matris[k][1]++;
                }
            }
        }
        if(temp!=0)
        k++;
        temp=0;
    }

    printf("%d %d",matris[0][0],matris[0][1]+1);
}

Answer 1

I think you should check that sayilar[i] is not in matris before doing the nested loop.

for(i=0; i<10; i++)
{
    int found = 0;
    for (int l=0; l<k; l++)
    {
       if (matris[l][0] == sayilar[i]) { found = 1; break; }
    }

    if (!found) 
    {
        for(j=i+1; j<10; j++)
        {
            //...

If you want more advanced solution you can sort the array, which has O(nlogn) complexity, and than just simply iterate thru the sorted array... Just for inspiration.

Answer 2

Ideally, you'd like to do this in one pass, rather than using the nested loops. The best way is to use some sort of mapping structure, where the map key is the value you're counting, and the map value is the number of occurences for that value.

For this specific example, the easiest thing to do would be to create a single-dimensioned array, where the index corresponds to the value you're counting. Example:

int sayilar[10]={5,6,2,1,4,2,5,5,5,2};  
size_t counts[10] = {0};
size_t dups = 0;
...
for (i = 0; i < 10; i++)
{
  /**
   * Add one to the value of counts[k], where k == sayilar[i]
   */
  counts[sayilar[i]]++;

  /**
   * If the count is equal to 2, add one to the value
   * of dups.  We use == 2 instead of > 1 so that we
   * only count unique duplicates.  
   */
  if (counts[sayilar[i]] == 2)
  {
    dups++;
  }
}

So as this loop executes, counts gets updated as follows:

counts[5] = 1;
counts[6] = 1;
counts[2] = 1;
counts[1] = 1;
counts[4] = 1;
counts[2] = 2; dups = 1;
counts[5] = 2; dups = 2;
counts[5] = 3;
counts[5] = 4;
counts[2] = 3;

Unfortunately, this approach doesn't scale very well if you're tracking a very wide range of values, or values that aren't integers.

Languages like C++ and Java provide a built-in map data type which is usually built on top of some sort of balanced tree structure like a Red-Black tree, which is beyond overkill for this particular problem.

Answer 3

Do you know anything about the numbers in the array?

If you know, for instance, that they will all be between 1 and 10, then you could just create an array of size 10 which would contain the count for each number.

Something like this (not tested)

int sayilar[] = {5,6,2,1,4,2,5,5,5,2};
int counts[10] = {};

for( int i=0; i<10; ++i)
{
    ++counts[sayilar[i]-1];
}

// Now the 'counts' array has:
// counts[0] == 1     - indicating one '1' found
// counts[1] == 3     - indicating three '2' found
// counts[2] == 0     - indicating zero '3' found
// etc.

If you don't have any guarantees about what values might be in sayilar, then sorting first is probably the best option, as others have mentioned. Check out qsort, which will sort your array in-place.

Answer 4

If I were writing it, I'd do it in two stages.

First, I'd loop over the array, and count instances of each:

int counts[5] = { 0,0,0,0,0 };

for ( int i=0 ; i < 10 ; ++i ) {
   counts[ sayilar[i] - 1 ] += 1;
}

Next, I would loop over and look for duplicates:

for( int i=0 ; i < 5 ; ++i ) {
   if ( counts[i] > 1 ) {
      printf("Duplicate found: %d with %d instances\n", i+1, counts[i] );
   }
}

This approach leaves it much more readable.