Skip to content

Instantly share code, notes, and snippets.

@juliafealves
Last active October 21, 2018 01:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save juliafealves/0ce681cac7cf6a95c9763b46c2f0bdf8 to your computer and use it in GitHub Desktop.
Save juliafealves/0ce681cac7cf6a95c9763b46c2f0bdf8 to your computer and use it in GitHub Desktop.
🔝 Dado um array de inteiros contendo duplicatas, retornar o elemento majoritátio se ele existe. Um elemento majoritário aparece mais que n/2 vezes, onde n é o tamanho do array.
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* Dado um array de inteiros contendo duplicatas, retornar o elemento majoritátio se ele existe. Um elemento majoritário
* aparece mais que n/2 vezes, onde n é o tamanho do array. Exemplo:
*
* Input:
* array = [2,8,7,2,2,5,2,3,1,2,2]
* Output:
* Elemento majoritario é 2
*
* Dica: podemos usar tabelas hash para resolver o problema em O(n). A ideia é varre o array e armazenar o par
* (elemento, frequencia) na tabela (sel ele já existe entao a frequencia é incrementada) e depois buscar o elemento
* cuja frequencia é maior que n/2.
*/
public class ElementoMajoritario {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Informe o array separado por vírgula:");
String[] array = scanner.nextLine().trim().split(",");
int[] numeros = new int[array.length];
for (int i = 0; i < array.length; i++) {
numeros[i] = Integer.parseInt(array[i]);
}
Integer majaritario = encontrarElementoMajoritario(numeros);
if (majaritario != null) {
System.out.println("Elemento majoritário é " + majaritario);
} else {
System.out.println("Nenhuma elemento majoritário.");
}
}
/**
* Encontra o elemento majoritário na lista.
* @param numeros
* @return
*/
static Integer encontrarElementoMajoritario(int[] numeros) {
Integer numero = null;
if (numeros.length > 0) {
Map<Integer, Integer> contador = new HashMap<>();
for (int i = 0; i < numeros.length; i++) {
int indice = numeros[i];
if (!contador.containsKey(indice)) {
contador.put(indice, 1);
} else {
int valor = contador.get(indice);
contador.put(indice, valor + 1);
}
}
int frequencia = numeros.length / 2;
for (Integer chave : contador.keySet()) {
if (contador.get(chave) > frequencia) {
numero = chave;
}
}
}
return numero;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment