c - Find duplicates and number of times -

i have write program finds duplicate in array , how many times every duplicate present in array. code:

#include <stdio.h> #include <stdlib.h>  #define dim 5  int contains (int v[], int dim, int n);  int main(int argc, char** argv)  {     int i, j, k = 0, found;     int v[dim];     int dup[dim] = {0};      (i = 0; < dim; i++)     {         printf("insert element in array: ");         scanf("%d", &v[i]);     }      (i = 0; < dim; i++)     {         found = 0;          if (contains (dup, dim, v[i]) == 0)         {             (j = 0; j < dim; j++)             {                 if (v[i] == v[j] && (i != j))                 {                     found ++;                     dup[k] = v[i];                     k++;                 }             }             if (found != 0)             {                 printf("element %d has been repeated %d times\n", v[i], found);             }         }     }       return (0); }   int contains (int v[], int dim, int n) {     int i;     int found = 0;      (i = 0; < dim; i++)     {         if (v[i] == n)         {             found = 1;         }     }      return found; } 

the program works quite think not efficient. surely exists way have program efficient, isn't it? mean way continue using array , not other structure

a hash table solves problem in linear time. if don't want muck data structures, here's o(n lg n) solution in c-like pseudocode:

// given: array of n integers  sort(a, n);  (int = 0;;) {     int value = a[i];     int count = 0;      {         i++;         count++;     } while (i < n && a[i] == value);      if (count > 1)         printf("element %d has been repeated %d times\n", value, count); } 

sorting can done qsort. rest of algorithm relies on fact that, after sorting, duplicates grouped together.