1

Questão:

"Faça um algoritmo para ler 50 números (coloquei 5 para testar) e armazenar em um vetor VET, verificar e escrever se existem números repetidos no vetor VET e em que posições se encontram"

Eu gostaria de refazer essa questão sem usar ArrayList ou Map. Até agora, o que eu consegui fazer foi mostrar os números que se repete e quantas vezes, mas não sei como dizer as posições que ele se repete.

Gostaria que a saída fosse assim, por exemplo:

"numero 2 se repete 3 vezes nas posicoes: [0,3,4]"
"numero 4 se repete 2 vezes nas posicoes: [1,2]"

No meu código a saída está assim, por exemplo:

"Numero 2 se repete 3 vezes"
"Numero 3 se repete 2 vezes"

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

    public static Scanner entrada = new Scanner(System.in);
    public static void main(String[] args) {
        
        List<Integer> lista = new ArrayList<Integer>(5);
        for(int i = 0;  i < 5; i++) {
            lista.add(entrada.nextInt());
        }
        Collections.sort(lista); // ordena a lista em ordem alfabética.

        Map<Integer, Integer> cont = new TreeMap<Integer, Integer>();
        for (int repeticao : lista) {
            if (!cont.containsKey(repeticao))
            cont.put(repeticao, 0);
            cont.put(repeticao, cont.get(repeticao) + 1);
        }
        
        for (Entry<Integer, Integer> entry : cont.entrySet()) {
            if(entry.getValue() > 1)
                System.out.printf("\nNumro %s se repete %d vezes", entry.getKey(), entry.getValue());
        }

    }

}
1
  • 1
    Sem usar Map teria que simular um com um Array de Arrays no formato [[key1, value1], [key2, value2]....[keyN, valueN]]. Além do problema da implementação essa condição vem acompanhada da incrível perda de desempenho pois Tabelas de Hash(HashMap) apresentam complexidade de tempo O(1) em operações de busca, Arvores Binárias(TreeMap) apresentam complexidade de tempo O(log n) em operações de busca, enquanto Arrays apresentam complexidade de tempo O(n) em operações de busca. Commented 2/05/2022 às 16:55

1 Resposta 1

2

Sem usar ArrayList até dá, basta trocar para um array. Mas sem Map fica desnecessariamente mais complicado, não vejo motivo para fazer de outra forma.


Com Map (mantendo o ArrayList)

Em vez de Map<Integer, Integer>, use um Map<Integer, List<Integer>>, que para cada número, guarda uma lista das posições em que o número aparece. Depois, na hora de imprimir, basta mostrar apenas os que aparecem em mais de uma posição.

List<Integer> numeros = new ArrayList<>();
for (int i = 0; i < 50; i++) {
    numeros.add(entrada.nextInt());
}

Map<Integer, List<Integer>> cont = new LinkedHashMap<>();
for (int i = 0; i < numeros.size(); i++) {
    int n = numeros.get(i);
    if (!cont.containsKey(n)) {
        cont.put(n, new ArrayList<>());
    }
    // adiciona "i" na lista de posições em que o número aparece
    cont.get(n).add(i);
}

for (Entry<Integer, List<Integer>> entry : cont.entrySet()) {
    List<Integer> posicoes = entry.getValue();
    if (posicoes.size() > 1) {
        System.out.printf("Número %d se repete %d vezes nas posições: %s\n", entry.getKey(), posicoes.size(), posicoes);
    }
}

Troquei o TreeMap (que guardaria os números em ordem crescente) para LinkedHashMap, que guarda os números na ordem em que foram inseridos (o que parece estar mais de acordo com o que precisa: por exemplo, se digitar "1 2 3 2 1", no final mostrará primeiro 1 e depois o 2). Mas se a ordem deles tanto faz (pois o que interessa é apenas se eles se repetem), poderia trocar para HashMap sem problemas.


Com Map e array

Já se fosse com array, seria assim:

int[] numeros = new int[50];
for (int i = 0; i < numeros.length; i++) {
    numeros[i] = entrada.nextInt();
}

Map<Integer, List<Integer>> cont = new LinkedHashMap<>();
for (int i = 0; i < numeros.length; i++) {
    int n = numeros[i];
    if (!cont.containsKey(n)) {
        cont.put(n, new ArrayList<>());
    }
    cont.get(n).add(i);
}

// restante é igual

Na verdade daria para computar tudo no mesmo loop que lê os dados:

Map<Integer, List<Integer>> cont = new LinkedHashMap<>();
for (int i = 0; i < 50; i++) {
    int n = entrada.nextInt();
    if (!cont.containsKey(n)) {
        cont.put(n, new ArrayList<>());
    }
    cont.get(n).add(i);
    numeros[i] = n;
}

E na verdade, nem precisaria do array para guardar os números, afinal, se você só quer saber os números que foram digitados mais de uma vez (e a "posição" seria relativa à ordem em que eles foram digitados), ter apenas o Map já seria suficiente.


Sem Map

Se não quer usar Map, você teria que implementar manualmente o mapeamento entre cada elemento e suas respectivas posições.

Esta é a pior opção, pois consiste em basicamente reiventar a roda (e possivelmente de um jeito pior).

Claro, você até poderia fazer um loop pelos números, e para cada um, contar quantas vezes cada um ocorre e imprimir as posições, mas é algo tão pior e mais ineficiente que não vale a pena se desfazer do Map.

3
  • 1
    Muito obrigado. Eu conseguir resolver de um jeito muito mais simples, mas provavelmente menos eficiente. O problema é que eu ainda não entendo bem essas estruturas de dados como map, LinkedHash, TreeMap, etc...eu ainda não estou nesse nível, por isso queria uma solução que eu pudesse entender. O que eu fiz foi pegar o array normal, mais um array sem as repeticoes do primeiro e mais uma lista para guardar as posicoes que se repetem e a quantidade de vezes, que é o tamanho do array list. Depois de cada loop eu dei um clear() na lista. Mas obrigado pela resposta, vou estudar seu codigo pra upar. Commented 3/05/2022 às 12:37
  • 1
    O ruim é que não fica salvo essas informações, minha intençao era somente imprimir na tela as informações, mas se perdem a cada loop. Sua solução realmente é a melhor, eu tenho que estudar map urgentemente. Commented 3/05/2022 às 13:00
  • 2
    @pauloestevão, veja se o ajuda nos estudos pt.stackoverflow.com/a/515971/137387 Commented 4/05/2022 às 11:26

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 .