Cómo comprobar si un array tiene elementos duplicados en Java

Introducción

En este laboratorio, aprenderás cómo comprobar si un array tiene elementos duplicados en Java utilizando diferentes enfoques. Comenzaremos con un método fundamental que utiliza bucles anidados, lo que proporciona una comprensión clara del proceso de comparación.

A continuación, exploraremos una técnica más eficiente que utiliza la estructura de datos HashSet, demostrando cómo aprovechar las colecciones de Java para detectar duplicados de manera más rápida. Finalmente, examinaremos cómo ordenar el array puede simplificar el proceso de identificación de duplicados. Al final de este laboratorio, estarás equipado con múltiples estrategias para manejar elementos duplicados en arrays de Java.

Utilizar bucles anidados para encontrar duplicados

En este paso, exploraremos un enfoque fundamental para encontrar elementos duplicados dentro de un array utilizando bucles anidados en Java. Este método es sencillo y fácil de entender, lo que lo convierte en un buen punto de partida para aprender sobre la manipulación de arrays y el diseño básico de algoritmos.

Primero, creemos un nuevo archivo Java llamado FindDuplicatesNested.java en el directorio ~/project. Puedes hacer esto directamente en el Explorador de Archivos del WebIDE haciendo clic derecho en la carpeta project y seleccionando "Nuevo Archivo", luego escribiendo el nombre.

Ahora, abre el archivo FindDuplicatesNested.java en el Editor de Código y agrega el siguiente 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]);
                }
            }
        }
    }
}

Analicemos este código:

int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};: Esta línea declara un array de enteros llamado numbers y lo inicializa con algunos valores, incluyendo duplicados.
for (int i = 0; i < numbers.length; i++): Este es el bucle exterior. Itera a través de cada elemento del array utilizando un índice i.
for (int j = i + 1; j < numbers.length; j++): Este es el bucle interior. Para cada elemento en el índice i, itera a través de los elementos restantes del array comenzando desde el elemento después del índice i. Esto es importante para evitar comparar un elemento consigo mismo y para evitar encontrar el mismo par de duplicados dos veces (por ejemplo, comparar el índice 1 con el índice 4 y luego el índice 4 con el índice 1).
if (numbers[i] == numbers[j]): Esta condición verifica si el elemento en el índice i es igual al elemento en el índice j. Si son iguales, significa que hemos encontrado un duplicado.
System.out.println("Duplicate found: " + numbers[j]);: Si se encuentra un duplicado, esta línea imprime un mensaje que indica el elemento duplicado.

Guarda el archivo presionando Ctrl + S (o Cmd + S en macOS).

Ahora, abre la Terminal en la parte inferior del WebIDE. Asegúrate de estar en el directorio ~/project. Puedes confirmar esto escribiendo pwd y presionando Enter. La salida debe ser /home/labex/project.

Compila el código Java utilizando el comando javac:

javac FindDuplicatesNested.java

Si no hay errores, la compilación será exitosa y se creará un archivo FindDuplicatesNested.class en el directorio ~/project. Puedes verificar esto escribiendo ls y presionando Enter.

Finalmente, ejecuta el programa Java compilado utilizando el comando java:

java FindDuplicatesNested

Deberías ver la salida que indica los elementos duplicados encontrados por el programa.

Este enfoque de bucles anidados funciona comparando cada posible par de elementos en el array. Si bien es fácil de entender, puede volverse ineficiente para arrays muy grandes. En los siguientes pasos, exploraremos formas más eficientes de encontrar duplicados.

Utilizar HashSet para una comprobación eficiente de duplicados

En el paso anterior, utilizamos bucles anidados para encontrar duplicados, lo cual es sencillo pero puede ser lento para arrays grandes. En este paso, aprenderemos una forma más eficiente de encontrar duplicados utilizando un HashSet.

Un HashSet es una colección en Java que almacena elementos únicos. Esto significa que si intentas agregar un elemento que ya está en el HashSet, la operación de adición fallará (o más bien, devolverá false). Podemos aprovechar esta propiedad para detectar duplicados de manera eficiente.

Aquí está la idea: iteramos a través del array y, para cada elemento, intentamos agregarlo a un HashSet. Si el método add() devuelve false, significa que el elemento ya está en el conjunto y, por lo tanto, es un duplicado.

Creemos un nuevo archivo Java llamado FindDuplicatesHashSet.java en el directorio ~/project.

Abre el archivo FindDuplicatesHashSet.java en el Editor de Código y agrega el siguiente 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);
            }
        }
    }
}

Veamos las nuevas partes de este código:

import java.util.HashSet; y import java.util.Set;: Estas líneas importan las clases necesarias para utilizar HashSet.
Set<Integer> uniqueElements = new HashSet<>();: Esta línea crea un HashSet vacío que almacenará objetos Integer. Utilizamos Set como tipo porque HashSet implementa la interfaz Set.
for (int number : numbers): Este es un bucle for mejorado (también conocido como bucle for-each), que es una forma conveniente de iterar a través de cada elemento del array numbers.
!uniqueElements.add(number): Esta es la lógica central. uniqueElements.add(number) intenta agregar el number actual al HashSet. Si el número ya está presente, add() devuelve false. El operador ! niega este resultado, por lo que la condición if es verdadera solo cuando add() devuelve false, lo que indica un duplicado.

Guarda el archivo (Ctrl + S o Cmd + S).

Ahora, compila el código Java en la Terminal:

javac FindDuplicatesHashSet.java

Si la compilación es exitosa, ejecuta el programa:

java FindDuplicatesHashSet

Deberías ver la salida que enumera los elementos duplicados encontrados utilizando el método HashSet. Observa que este método es generalmente más rápido que el enfoque de bucles anidados, especialmente para arrays más grandes, porque agregar y comprobar elementos en un HashSet es muy eficiente.

Probar con un array ordenado

En este último paso, exploraremos otro enfoque para encontrar duplicados, específicamente cuando el array está ordenado. Si un array está ordenado, los elementos duplicados siempre estarán adyacentes entre sí. Esto permite una forma muy simple y eficiente de encontrar duplicados simplemente comparando elementos adyacentes.

Primero, creemos un nuevo archivo Java llamado FindDuplicatesSorted.java en el directorio ~/project.

Abre el archivo FindDuplicatesSorted.java en el Editor de Código y agrega el siguiente 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]);
            }
        }
    }
}

Examinemos las partes clave de este código:

import java.util.Arrays;: Esta línea importa la clase Arrays, que proporciona métodos de utilidad para arrays, incluyendo la ordenación.
Arrays.sort(numbers);: Esta línea ordena el array numbers en orden ascendente.
for (int i = 0; i < numbers.length - 1; i++): Este bucle itera a través del array ordenado. Iteramos hasta numbers.length - 1 porque estamos comparando el elemento actual (numbers[i]) con el siguiente elemento (numbers[i + 1]).
if (numbers[i] == numbers[i + 1]): Esta condición verifica si el elemento actual es igual al siguiente elemento. Si son iguales, significa que hemos encontrado un duplicado.

Guarda el archivo (Ctrl + S o Cmd + S).

Ahora, compila el código Java en la Terminal:

javac FindDuplicatesSorted.java

Si la compilación es exitosa, ejecuta el programa:

java FindDuplicatesSorted

Deberías ver la salida que enumera los elementos duplicados encontrados. Observa que debido a que el array está ordenado, los duplicados aparecerán consecutivamente en la salida.

Este método es muy eficiente para arrays ordenados ya que solo requiere un solo recorrido por el array después de la ordenación. Sin embargo, el paso inicial de ordenación en sí tiene un costo de tiempo, que depende del algoritmo de ordenación utilizado por Arrays.sort(). Para tipos primitivos como int, Arrays.sort() de Java utiliza un quicksort de doble pivote, que tiene una complejidad temporal promedio de O(n log n).

Ahora has explorado tres formas diferentes de encontrar duplicados en un array en Java: utilizando bucles anidados, utilizando un HashSet y utilizando un array ordenado. Cada método tiene sus propias compensaciones en términos de simplicidad, eficiencia y requisitos (como el array estar ordenado). Comprender estos diferentes enfoques es valioso para elegir el método más adecuado para un problema dado.

Resumen

En este laboratorio (lab), exploramos diferentes métodos para comprobar si un array contiene elementos duplicados en Java. Comenzamos implementando un enfoque sencillo utilizando bucles anidados, que consiste en comparar cada elemento con todos los demás elementos del array. Este método, aunque fácil de entender, tiene una complejidad temporal de O(n^2), lo que lo hace menos eficiente para arrays grandes.

A continuación, aprendimos cómo aprovechar la estructura de datos HashSet para una comprobación de duplicados más eficiente. Al iterar a través del array e intentar agregar cada elemento a un HashSet, podemos determinar rápidamente si un elemento es un duplicado porque el método add() de HashSet devuelve false si el elemento ya existe. Este enfoque ofrece una complejidad temporal significativamente mejorada, generalmente O(n) en promedio. Finalmente, consideramos cómo ordenar primero el array también se puede utilizar para encontrar duplicados de manera eficiente, ya que los elementos duplicados estarán adyacentes después de la ordenación.