6

Em uma array, exemplo [1, 2, 3, 4, 5, 2, 2, 3], quais lógicas, métodos e funções posso usar para pegar o valor com a maior ocorrência, como neste exemplo o 2.

3 Respostas 3

5

1. Método "ingênuo" - O(n2)

Para cada elemento do array, percorra o array inteiro contando quantas vezes aquele elemento aparece. Se o número for maior do que o maior encontrado até então, atualize, senão vá pro próximo.

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>";

Embora esse método seja referido como "ingênuo", para entradas pequenas ele pode ser até o mais eficiente de todos (pois não possui o overhead de uma estrutura de dados mais complexa).

2. Ordenação - O(n*log2 n)

Ordene o array (se ele já estiver ordenado, melhor ainda!) e então percorra-o procurando a maior sequência de elementos contíguos.

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>";

Esse método é mais eficiente que o método ingênuo para entradas maiores, porém menos eficiente que os métodos descritos a seguir. Entretanto, se por alguma razão seu array já estiver ordenado - ou se ordená-lo lhe der alguma vantagem futura (vai que você precisa usá-lo em um outro algoritmo que também funciona melhor com entradas ordenadas) - pode ser uma boa opção.

3. Tabela hash - O(n)

Crie uma tabela hash, inicialmente vazia. Para cada elemento do array, verifique se ele está na tabela. Se não estiver, acrescente-o com a contagem 1. Caso contrário, incremente a contagem. No final, percorra a tabela procurando o elemento com a maior contagem.

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>";

Você pode substituir essa tabela hash por uma árvore, se comparar elementos for mais "barato" que calcular o hash dos mesmos (raro, mas pode haver situações em que isso é verdade). Nesse caso a solução seria O(n*log2 n).

4. Array de contagens - O(n)

Esse método é mais rápido que o da tabela hash, mas só se aplica se o conjunto de valores possíveis for finito, não muito grande e conhecidos a priori.

Crie um array onde cada índice representa um elemento, iniciado com zero. Para cada elemento da sua entrada, incremente o valor correspondente ao mesmo no array. No final, percorra o array procurando o elemento com a maior contagem.

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?

Estes são alguns exemplos de técnicas, podem ser overkill para um problema tão simples, mas ilustram como situações particulares podem se beneficiar de algoritmos bem-adaptados ao seu contexto.

Um outro exemplo que não detalhei seria o "dividir e conquistar", que pode ser interessante (ao menos em teoria) se você possui vários processadores disponíveis para auxiliar na tarefa (ex.: GPGPU). Nesse caso você daria a cada processador a responsabilidade de contar um elemento (método ingênuo) e - no final - compararia as contagens de todos eles (apesar de haver certo "desperdício", como todos executariam em paralelo o resultado final seria O(n) tal como os melhores algoritmos).

2

Eu pensei numa logica que você poderia guardar os contadores num Object e utilizando apenas o forEach do Array.

Como ficou:

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;
}
1
  • Se você quiser retornar o contador de cada item, basta retornar a variavel b.
    – akira-ito
    Commented 19/11/2015 às 16:03
0

Melhor solução que encontrei:

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
1
  • Bem compacto, mas faltou a segunda parte, não? Descobrir qual é o elemento que aparece mais. Além disso, uma explicação sobre o que o código faz também seria muito bem-vinda (eu entendi, mas quem não tem familiaridade com o reduce pode ficar meio perdido).
    – mgibsonbr
    Commented 19/11/2015 às 15:58

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .