Array value with the highest occurrence

6

In an array, example [1, 2, 3, 4, 5, 2, 2, 3] , which logic, methods and functions I can use to get the value with the highest occurrence, as in this example 2 .

    
asked by anonymous 19.11.2015 / 14:00

3 answers

3

1. Method "naive" - O (n 2 )

For each element of the array, scroll through the entire array by counting how many times that element appears. If the number is greater than the largest one found so far, update, otherwise go to next.

var entrada = [1, 2, 3, 4, 5, 2, 2, 3];

var maior = null;
var ocorrenciasMaior = -1;

for ( var i = 0 ; i < entrada.length ; i++ ) {
  var ocorrencias = 1;
  for ( var t = i+1 ; t < entrada.length ; t++ )
    if ( entrada[i] == entrada[t] )
      ocorrencias++;
  
  if ( ocorrencias > ocorrenciasMaior ) {
    maior = entrada[i];
    ocorrenciasMaior = ocorrencias;
  }
}

document.body.innerHTML += "<p>" + maior + " (" + ocorrenciasMaior + " ocorrências)</p>";

While this method is referred to as "naive", for small inputs it may be even the most efficient of all (because it does not have the overhead of a more complex data structure). >

2. Ordering - O (n * log 2 n)

Sort the array (if it's already sorted, even better!) and then scroll through it for the largest sequence of contiguous elements.

var entrada = [1, 2, 3, 4, 5, 2, 2, 3];

entrada.sort();

var maior = null;
var ocorrenciasMaior = -1;

var contagem = 1;
for ( var i = 1 ; i <= entrada.length ; i++ ) {
  if ( i < entrada.length && entrada[i] == entrada[i-contagem] )
    contagem++;
  
  else if ( contagem > ocorrenciasMaior ) {
    maior = entrada[i-1];
    ocorrenciasMaior = contagem;
  }
}

document.body.innerHTML += "<p>" + maior + " (" + ocorrenciasMaior + " ocorrências)</p>";

This method is more efficient than the naive method for larger inputs, but less efficient than the methods described below. However, if for some reason your array is already sorted - or if you sort it gives you some future advantage (you need to use it in another algorithm that also works best with ordered entries) - it might be a good choice. / p>

3. Hashtable - O (n)

Create a hash table, initially empty. For each element of the array, make sure it is in the table. If it is not, add it with the count 1 . Otherwise, increase the count. At the end, scroll through the table looking for the element with the highest count.

var entrada = [1, 2, 3, 4, 5, 2, 2, 3];

var ocorrencias = {};

for ( var i = 0 ; i < entrada.length ; i++ )
  ocorrencias[entrada[i]] = 1 + (ocorrencias[entrada[i]] || 0);

var maior = null;
var ocorrenciasMaior = -1;

for ( var p in ocorrencias )
    if ( ocorrencias[p] > ocorrenciasMaior ) {
        maior = p;
        ocorrenciasMaior = ocorrencias[p];
    }

document.body.innerHTML += "<p>" + maior + " (" + ocorrenciasMaior + " ocorrências)</p>";

You can replace this hash table with a tree, if comparing elements is more "cheap" than calculating their hash (rare, but there may be situations where this is true). In this case the solution would be O (n * log 2 n).

4. Counting Array - O (n)

This method is faster than the hash table, but only applies if the set of possible values is finite, not too large and known a priori .

Create an array where each index represents an element, starting with zero. For each element of your input, increment the value corresponding to it in the array. At the end, scroll through the array looking for the element with the highest count.

var entrada = [1, 2, 3, 4, 5, 2, 2, 3];

var MAXIMO_VALOR = 10;
var ocorrencias = Array(MAXIMO_VALOR).fill(0);

for ( var i = 0 ; i < entrada.length ; i++ )
  ocorrencias[entrada[i]] = 1 + (ocorrencias[entrada[i]] || 0);

var maior = null;
var ocorrenciasMaior = -1;

for ( var i = 0 ; i < ocorrencias.length ; i++ )
    if ( ocorrencias[i] > ocorrenciasMaior ) {
        maior = i;
        ocorrenciasMaior = ocorrencias[i];
    }

document.body.innerHTML += "<p>" + maior + " (" + ocorrenciasMaior + " ocorrências)</p>";

Etc

These are some examples of techniques, they may be overkill for such a simple problem, but illustrate how particular situations can benefit from well-adapted algorithms.

Another example I did not detail would be "divide and conquer", which may be interesting (at least in theory) if you have multiple processors available to assist the task (eg GPGPU ). In this case you would give each processor the responsibility of counting an element (naive method) and - in the end - would compare the counts of all of them (although there is some "waste", as all would run in parallel the end result would be O (n) such as the best algorithms).

    
19.11.2015 / 16:55
2

I thought of a logic that you could save the counters in an Object and using only the Array forEach.

How it was:

function maior(arr){
 if (!arr) return null;
 var b={}, g = arr[0];
 arr.forEach(function(f){
  if (!b[f]) b[f] = 0;
  b[f] += 1;
  if(b[f]>b[g]) g=f;
 })
 return g;
}
    
19.11.2015 / 16:56
0

Best solution I found:

var arr = [1, 2, 3, 4, 5, 2, 2, 3];

var qtd = arr.reduce(function(acc,e){acc[e] = (e in acc ? acc[e]+1 : 1); return acc}, {});

qtd['2']; //3
    
19.11.2015 / 14:08