[C++] array

[Andrea Simonassi]

prova questa, ordina l'array e poi conta la lunghezza dei gruppi di valori
esempio
1,1,1,1,3,3,3,3,3,5,5,6,6,7,7

gruppo 1 lungo 4
gruppo 3 lungo 5,
gruppo 5 lungo 2
.....

vince il gruppo piu lungo

#include <algorithm>
int freq(int*a, size_t a_len)
{
  int*b=&a[a_len];
  int cur, c_cur=0, best, c_best=0; 	

  std::sort(a, b);

  while(a<b)
  {
    cur = *a++;
    if(++c_cur > c_best)c_best=c_cur, best=cur;
    if(*a!=cur)c_cur=0;
  }
  return best;
}

Complessita O(NlogN(se l'algoritmo di sort e' efficiente) + n(la scansione dell'array ordinato)), circa uguale a =(NlogN)

oppure crea una mappa in memoria dove associ i valori trovati nell'array a un conteggio, se conosci la STL

#include <map>
int freq(int*a, size_t a_len)
{
  int*b=&a[a_len];
	
  std::map<int,int>m;
  std::pair<std::map<int,int>::iterator ,bool>i;

  int best, c_best;

  while(a<b)
  {
    if(i = m.insert(std::map<int,int>::value_type (*a, 1)), !i.second) 
    i.first->second ++;
    if(i.first->second>c_best)    
      best = *a, c_best=i.first->second;
    ++a;
  }
  return best;
}

in questo caso la complessita' e' O(N) + la complessita' dell'insert nella mappa che non conosco