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