Last active
October 21, 2018 01:27
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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