Como Verificar se um Array Possui Elementos Duplicados em Java

Introdução

Neste laboratório, você aprenderá como verificar se um array possui elementos duplicados em Java usando diferentes abordagens. Começaremos com um método fundamental usando loops aninhados, que fornece uma compreensão clara do processo de comparação.

Em seguida, exploraremos uma técnica mais eficiente utilizando a estrutura de dados HashSet, demonstrando como aproveitar as coleções Java para uma detecção de duplicatas mais rápida. Finalmente, examinaremos como a ordenação do array pode simplificar o processo de identificação de duplicatas. Ao final deste laboratório, você estará equipado com múltiplas estratégias para lidar com elementos duplicados em arrays Java.

Usar Loops Aninhados para Duplicatas

Nesta etapa, exploraremos uma abordagem fundamental para encontrar elementos duplicados dentro de um array usando loops aninhados em Java. Este método é direto e fácil de entender, tornando-o um bom ponto de partida para aprender sobre manipulação de arrays e design de algoritmos básicos.

Primeiro, vamos criar um novo arquivo Java chamado FindDuplicatesNested.java em seu diretório ~/project. Você pode fazer isso diretamente no Explorador de Arquivos do WebIDE, clicando com o botão direito na pasta project e selecionando "Novo Arquivo", em seguida, digitando o nome.

Agora, abra o arquivo FindDuplicatesNested.java no Editor de Código e adicione o seguinte código Java:

public class FindDuplicatesNested {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        System.out.println("Finding duplicate elements using nested loops:");

        // Use nested loops to compare each element with every other element
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                // If a duplicate is found (elements are equal and not the same element)
                if (numbers[i] == numbers[j]) {
                    System.out.println("Duplicate found: " + numbers[j]);
                }
            }
        }
    }
}

Vamos detalhar este código:

• int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};: Esta linha declara um array de inteiros chamado numbers e o inicializa com alguns valores, incluindo duplicatas.
• for (int i = 0; i < numbers.length; i++): Este é o loop externo. Ele itera por cada elemento do array usando um índice i.
• for (int j = i + 1; j < numbers.length; j++): Este é o loop interno. Para cada elemento no índice i, ele itera pelos elementos restantes do array, começando pelo elemento após o índice i. Isso é importante para evitar comparar um elemento consigo mesmo e para evitar encontrar o mesmo par de duplicatas duas vezes (por exemplo, comparar o índice 1 com o índice 4 e depois o índice 4 com o índice 1).
• if (numbers[i] == numbers[j]): Esta condição verifica se o elemento no índice i é igual ao elemento no índice j. Se forem iguais, significa que encontramos uma duplicata.
• System.out.println("Duplicate found: " + numbers[j]);: Se uma duplicata for encontrada, esta linha imprime uma mensagem indicando o elemento duplicado.

Salve o arquivo pressionando Ctrl + S (ou Cmd + S no macOS).

Agora, abra o Terminal na parte inferior do WebIDE. Certifique-se de estar no diretório ~/project. Você pode confirmar isso digitando pwd e pressionando Enter. A saída deve ser /home/labex/project.

Compile o código Java usando o comando javac:

javac FindDuplicatesNested.java

Se não houver erros, a compilação será bem-sucedida e um arquivo FindDuplicatesNested.class será criado no diretório ~/project. Você pode verificar isso digitando ls e pressionando Enter.

Finalmente, execute o programa Java compilado usando o comando java:

java FindDuplicatesNested

Você deve ver a saída indicando os elementos duplicados encontrados pelo programa.

Esta abordagem de loop aninhado funciona comparando cada par possível de elementos no array. Embora seja simples de entender, pode se tornar ineficiente para arrays muito grandes. Nas próximas etapas, exploraremos maneiras mais eficientes de encontrar duplicatas.

Usar HashSet para Verificação Eficiente de Duplicatas

Na etapa anterior, usamos loops aninhados para encontrar duplicatas, o que é simples, mas pode ser lento para arrays grandes. Nesta etapa, aprenderemos uma maneira mais eficiente de encontrar duplicatas usando um HashSet.

Um HashSet é uma coleção em Java que armazena elementos únicos. Isso significa que, se você tentar adicionar um elemento que já está no HashSet, a operação de adição falhará (ou, mais precisamente, retornará false). Podemos aproveitar essa propriedade para detectar duplicatas de forma eficiente.

A ideia é a seguinte: iteramos pelo array e, para cada elemento, tentamos adicioná-lo a um HashSet. Se o método add() retornar false, significa que o elemento já está no conjunto e, portanto, é uma duplicata.

Vamos criar um novo arquivo Java chamado FindDuplicatesHashSet.java em seu diretório ~/project.

Abra o arquivo FindDuplicatesHashSet.java no Editor de Código e adicione o seguinte código Java:

import java.util.HashSet;
import java.util.Set;

public class FindDuplicatesHashSet {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // Create a HashSet to store unique elements
        Set<Integer> uniqueElements = new HashSet<>();

        System.out.println("Finding duplicate elements using HashSet:");

        // Iterate through the array
        for (int number : numbers) {
            // Try to add the element to the HashSet
            // If add() returns false, the element is a duplicate
            if (!uniqueElements.add(number)) {
                System.out.println("Duplicate found: " + number);
            }
        }
    }
}

Vamos analisar as novas partes deste código:

• import java.util.HashSet; e import java.util.Set;: Essas linhas importam as classes necessárias para usar HashSet.
• Set<Integer> uniqueElements = new HashSet<>();: Esta linha cria um HashSet vazio que armazenará objetos Integer. Usamos Set como o tipo porque HashSet implementa a interface Set.
• for (int number : numbers): Este é um loop for aprimorado (também conhecido como loop for-each), que é uma maneira conveniente de iterar por cada elemento do array numbers.
• !uniqueElements.add(number): Esta é a lógica principal. uniqueElements.add(number) tenta adicionar o number atual ao HashSet. Se o número já estiver presente, add() retorna false. O operador ! nega este resultado, então a condição if é verdadeira somente quando add() retorna false, indicando uma duplicata.

Salve o arquivo (Ctrl + S ou Cmd + S).

Agora, compile o código Java no Terminal:

javac FindDuplicatesHashSet.java

Se a compilação for bem-sucedida, execute o programa:

java FindDuplicatesHashSet

Você deve ver a saída listando os elementos duplicados encontrados usando o método HashSet. Observe que este método é geralmente mais rápido do que a abordagem de loop aninhado, especialmente para arrays maiores, porque adicionar e verificar elementos em um HashSet é muito eficiente.

Testar com Array Ordenado

Nesta etapa final, exploraremos outra abordagem para encontrar duplicatas, especificamente quando o array está ordenado. Se um array estiver ordenado, os elementos duplicados estarão sempre adjacentes uns aos outros. Isso permite uma maneira muito simples e eficiente de encontrar duplicatas, simplesmente comparando elementos adjacentes.

Primeiro, vamos criar um novo arquivo Java chamado FindDuplicatesSorted.java em seu diretório ~/project.

Abra o arquivo FindDuplicatesSorted.java no Editor de Código e adicione o seguinte código Java:

import java.util.Arrays;

public class FindDuplicatesSorted {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // First, sort the array
        Arrays.sort(numbers);

        System.out.println("Finding duplicate elements in a sorted array:");

        // Iterate through the sorted array and compare adjacent elements
        for (int i = 0; i < numbers.length - 1; i++) {
            // If the current element is equal to the next element, it's a duplicate
            if (numbers[i] == numbers[i + 1]) {
                System.out.println("Duplicate found: " + numbers[i]);
            }
        }
    }
}

Vamos examinar as partes principais deste código:

• import java.util.Arrays;: Esta linha importa a classe Arrays, que fornece métodos utilitários para arrays, incluindo a ordenação.
• Arrays.sort(numbers);: Esta linha ordena o array numbers em ordem crescente.
• for (int i = 0; i < numbers.length - 1; i++): Este loop itera pelo array ordenado. Iteramos até numbers.length - 1 porque estamos comparando o elemento atual (numbers[i]) com o próximo elemento (numbers[i + 1]).
• if (numbers[i] == numbers[i + 1]): Esta condição verifica se o elemento atual é igual ao próximo elemento. Se forem iguais, significa que encontramos uma duplicata.

Salve o arquivo (Ctrl + S ou Cmd + S).

Agora, compile o código Java no Terminal:

javac FindDuplicatesSorted.java

Se a compilação for bem-sucedida, execute o programa:

java FindDuplicatesSorted

Você deve ver a saída listando os elementos duplicados encontrados. Observe que, como o array está ordenado, as duplicatas aparecerão consecutivamente na saída.

Este método é muito eficiente para arrays ordenados, pois requer apenas uma única passagem pelo array após a ordenação. No entanto, a etapa inicial de ordenação em si tem um custo de tempo, que depende do algoritmo de ordenação usado por Arrays.sort(). Para tipos primitivos como int, o Arrays.sort() do Java usa um quicksort de pivô duplo, que tem uma complexidade de tempo média de O(n log n).

Você agora explorou três maneiras diferentes de encontrar duplicatas em um array em Java: usando loops aninhados, usando um HashSet e usando um array ordenado. Cada método tem suas próprias compensações em termos de simplicidade, eficiência e requisitos (como o array estar ordenado). Compreender essas diferentes abordagens é valioso para escolher o método mais adequado para um determinado problema.

Resumo

Neste laboratório, exploramos diferentes métodos para verificar se um array contém elementos duplicados em Java. Começamos implementando uma abordagem direta usando loops aninhados, que envolve comparar cada elemento com todos os outros elementos no array. Este método, embora fácil de entender, tem uma complexidade de tempo de O(n^2), tornando-o menos eficiente para arrays grandes.

Em seguida, aprendemos como aproveitar a estrutura de dados HashSet para uma verificação de duplicatas mais eficiente. Ao iterar pelo array e tentar adicionar cada elemento a um HashSet, podemos determinar rapidamente se um elemento é uma duplicata, porque o método add() do HashSet retorna false se o elemento já existir. Essa abordagem oferece uma complexidade de tempo significativamente aprimorada, tipicamente O(n) em média. Finalmente, consideramos como a ordenação do array primeiro também pode ser usada para encontrar duplicatas de forma eficiente, pois os elementos duplicados estarão adjacentes após a ordenação.