Programa Java para eliminar elementos duplicados de la array

Una array es una colección de elementos almacenados en ubicaciones de memoria contiguas. La idea es almacenar varios artículos del mismo tipo juntos. Para simplificar, podemos pensar en una array como una flota de escaleras donde en cada paso se coloca un valor

Dada una array, la tarea es eliminar los elementos duplicados de la array.

Ejemplos:

Input  : a[] = {1, 1, 2, 2, 2}
Output : a[] = {1,2}
         new size = 2

Input  : a[] = {5,2,6,8,6,7,5,2,8}
Output : a[] = {2,5,6,7,8}
         new size = 5

Las formas de eliminar elementos duplicados de la array:

1. Uso de espacio adicional
2. Espacio adicional constante
3. usando conjunto
4. Usando array de frecuencia
5. Usando HashMap

Método 1: (usando espacio adicional)

1. Cree una array temporal temp[] para almacenar elementos únicos.
2. Atraviese la array de entrada y copie todos los elementos únicos de a[] a temp[]. Además, lleva la cuenta de los elementos únicos. Sea esta cuenta j.
3. Copie j elementos de temp[] a a[].

Nota: este enfoque es aplicable cuando se ordena la array.

// Java Program to Remove Duplicate Elements
// From the Array using extra space
 
public class Main {
 
    public static int removeduplicates(int a[], int n)
    {
        if (n == 0 || n == 1) {
            return n;
        }
 
        // creating another array for only storing
        // the unique elements
        int[] temp = new int[n];
        int j = 0;
 
        for (int i = 0; i < n - 1; i++) {
            if (a[i] != a[i + 1]) {
                temp[j++] = a[i];
            }
        }
 
        temp[j++] = a[n - 1];
 
        // Changing the original array
        for (int i = 0; i < j; i++) {
            a[i] = temp[i];
        }
 
        return j;
    }
    public static void main(String[] args)
    {
        int a[] = { 1, 1, 2, 2, 2 };
        int n = a.length;
 
        n = removeduplicates(a, n);
 
        // Printing The array elements
        for (int i = 0; i < n; i++)
            System.out.print(a[i] + " ");
    }
}

1 2 

Complejidad de tiempo : O(n)

Espacio Auxiliar: O(n)

Método 2 : (espacio adicional constante)

Simplemente mantenga un índice separado para la misma array que se mantuvo para una array diferente en el Método 1.

// Java Program to Remove Duplicate Elements
// From the Array using extra space
 
public class Main {
    public static int removeDuplicates(int a[], int n)
    {
        // if(array size if 0 or 1 array is already sorted)
        if (n == 0 || n == 1) {
            return n;
        }
 
        int j = 0;
 
        // check if the ith element is not equal to
        // the (i+1)th element, then add that element
        // at the jth index in the same array
        // which indicates that te particular element
        // will only be added once in the array
        for (int i = 0; i < n - 1; i++) {
            if (a[i] != a[i + 1]) {
                a[j++] = a[i];
            }
        }
 
        a[j++] = a[n - 1];
 
        return j;
    }
 
    public static void main(String[] args)
    {
        int a[] = { 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6 };
 
        int n = a.length;
        
        int j=0;
       
        // the function will modify the array a[]
        // such that the starting j elements
        // will be having all unique elements
        // and no element will be appearing more than
        // once
        j = removeDuplicates(a, n);
 
        // printing array elements
        for (int i = 0; i < j; i++)
            System.out.print(a[i] + " ");
    }
}

1 2 3 4 5 6 

Complejidad de tiempo : O(n)

Espacio Auxiliar : O(1) 

Nota: Ambos métodos mencionados anteriormente se pueden usar si la array está ordenada. Entonces, para usar el método mencionado anteriormente, si la array no está ordenada, debe ordenar la array. Puede usar el método incorporado Arrays.sort() para ordenar la array. Si la clasificación de la array se realiza con este método, la complejidad del tiempo del programa aumenta de O(n) a O(nlogn) .

Método 3 : Uso del conjunto

Este método se puede usar incluso si la array no está ordenada.

Acercarse: 

1. tomar un conjunto
2. Inserta todos los elementos de la array en el Conjunto. Set no permite duplicados y conjuntos como LinkedHashSet mantienen el orden de inserción, por lo que eliminará los duplicados y los elementos se imprimirán en el mismo orden en que se insertan.
3. Imprimir elementos de Set.

// Java Program to Remove Duplicate Elements
// From the Array using Set
 
import java.util.*;
 
class GFG {
 
    // Function to remove duplicate from array
    public static void removeDuplicates(int[] a)
    {
        LinkedHashSet<Integer> set
            = new LinkedHashSet<Integer>();
 
        // adding elements to LinkedHashSet
        for (int i = 0; i < a.length; i++)
            set.add(a[i]);
 
        // Print the elements of LinkedHashSet
        System.out.print(set);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = {5,2,6,8,6,7,5,2,8};
     
        // Function call
        removeDuplicates(a);
    }
}

[5, 2, 6, 8, 7]

Método 4: Usar array de frecuencia

Podemos usar la array de frecuencias si el rango del número en la array es limitado, o también podemos usar una interfaz de conjunto o mapa para eliminar duplicados si el rango de números en la array es demasiado grande.

Acercarse:

1. Encuentre el elemento Máximo (m) en la array.
2. Cree una nueva array de tamaño m+1.
3. Ahora recorra la array de entrada y cuente la frecuencia de cada elemento en la array de entrada.
4. Ahora recorra la array de frecuencias y verifique la frecuencia de cada número, si la frecuencia del elemento en particular es mayor que 0, luego imprima el número.

// Java Program to Remove Duplicate Elements
// From the Array by maintaining frequency array
 
import java.util.*;
 
class GFG {
    public static void main(String[] args)
    {
        int a[] = { 5, 2, 6, 8, 6, 7, 5, 2, 8 };
        int n = a.length;
 
        // m will have the maximum element in the array.
        int m = 0;
 
        for (int i = 0; i < n; i++) {
            m = Math.max(m, a[i]);
        }
 
        // creating the frequency array
        int[] f = new int[m + 1];
 
        // initializing the f[] with 0
        for (int i = 0; i < m + 1; i++) {
            f[i] = 0;
        }
 
        // incrementing the value at a[i]th index
        // in the frequency array
        for (int i = 0; i < n; i++)
        {
            f[a[i]]++;
        }
 
        for (int i = 0; i < m + 1; i++)
        {
   
            // if the frequency of the particular element
            // is greater than 0, then print it once
            if (f[i] > 1) {
                System.out.print(i + " ");
            }
        }
    }
}

2 5 6 8 

Complejidad de tiempo : O(n)

Espacio Auxiliar : O(m)

Método 5: Usar HashMap 

El método de frecuencia anterior no será útil si el número es mayor que 10 ⁶ o si la array es de strings. En este caso, tenemos que usar HashMap.

Acercarse: 

• Cree un HashMap para almacenar los elementos únicos.
• Atraviesa la array.
• Compruebe si el elemento está presente en HashMap.
• En caso afirmativo, continúe recorriendo la array.
• De lo contrario, imprima el elemento y almacene el elemento en HashMap.

// Java Program to Remove Duplicate Elements
// From the Array using HashMap
 
import java.util.HashMap;
 
class GFG {
    static void removeDups(int[] a, int n)
    {
 
        // Hash map which will store the
        // elements which has appeared previously.
        HashMap<Integer, Boolean> mp = new HashMap<>();
 
        for (int i = 0; i < n; ++i) {
 
            // Print the element if it is not
            // present there in the hash map
            // and Insert the element in the hash map
            if (mp.get(a[i]) == null)
            {
                System.out.print(a[i] + " ");
                mp.put(a[i], true);
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 5, 1, 7, 2, 4, 2 };
       
        int n = arr.length;
        removeDups(arr, n);
    }
}

1 2 5 7 4 

Complejidad de tiempo : O(n)

Espacio Auxiliar : O(m)