Eliminar duplicados de la array ordenada

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

Ejemplos: 

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

Input  : arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}
Output : arr[] = {1, 2, 3, 4, 5}
         new size = 5

Método 1: (usando espacio extra) 

  1. Cree una array auxiliar temp[] para almacenar elementos únicos.
  2. Recorra la array de entrada y copie uno por uno los elementos únicos de arr[] a temp[]. También realice un seguimiento del recuento de elementos únicos. Sea este conteo j .
  3. Copie j elementos de temp[] a arr[] y devuelva j
 

Complete Interview Preparation - GFGImplementación:

C++

// Simple C++ program to remove duplicates
#include <iostream>
using namespace std;
 
// Function to remove duplicate elements This function
// returns new size of modified array.
int removeDuplicates(int arr[], int n)
{
    // Return, if array is empty or contains a single
    // element
    if (n == 0 || n == 1)
        return n;
 
    int temp[n];
 
    // Start traversing elements
    int j = 0;
    // If current element is not equal to next element
    // then store that current element
    for (int i = 0; i < n - 1; i++)
        if (arr[i] != arr[i + 1])
            temp[j++] = arr[i];
 
    // Store the last element as whether it is unique or
    // repeated, it hasn't stored previously
    temp[j++] = arr[n - 1];
 
    // Modify original array
    for (int i = 0; i < j; i++)
        arr[i] = temp[i];
 
    return j;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // removeDuplicates() returns new size of array.
    n = removeDuplicates(arr, n);
 
    // Print updated array
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// Simple C program to remove duplicates
#include <stdio.h>
 
// Function to remove duplicate elements This function
// returns new size of modified array.
int removeDuplicates(int arr[], int n)
{
    // Return, if array is empty or contains a single
    // element
    if (n == 0 || n == 1)
        return n;
 
    int temp[n];
 
    // Start traversing elements
    int j = 0;
    // If current element is not equal to next element
    // then store that current element
    for (int i = 0; i < n - 1; i++)
        if (arr[i] != arr[i + 1])
            temp[j++] = arr[i];
 
    // Store the last element as whether it is unique or
    // repeated, it hasn't stored previously
    temp[j++] = arr[n - 1];
 
    // Modify original array
    for (int i = 0; i < j; i++)
        arr[i] = temp[i];
 
    return j;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // removeDuplicates() returns new size of array.
    n = removeDuplicates(arr, n);
 
    // Print updated array
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// simple java program to remove duplicates
 
class Main {
    // Function to remove duplicate elements This function
    // returns new size of modified array.
    static int removeDuplicates(int arr[], int n)
    {
        // Return, if array is empty or contains a single
        // element
        if (n == 0 || n == 1)
            return n;
 
        int[] temp = new int[n];
 
        // Start traversing elements
        int j = 0;
        for (int i = 0; i < n - 1; i++)
            // If current element is not equal to next
            // element then store that current element
            if (arr[i] != arr[i + 1])
                temp[j++] = arr[i];
 
        // Store the last element as whether it is unique or
        // repeated, it hasn't stored previously
        temp[j++] = arr[n - 1];
 
        // Modify original array
        for (int i = 0; i < j; i++)
            arr[i] = temp[i];
 
        return j;
    }
 
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };
        int n = arr.length;
 
        n = removeDuplicates(arr, n);
 
        // Print updated array
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python3 program to
# remove duplicates
# Function to remove
# duplicate elements
 
# This function returns
# new size of modified
# array.
def removeDuplicates(arr, n):
 
    # Return, if array is
    # empty or contains
    # a single element
    if n == 0 or n == 1:
        return n
 
    temp = list(range(n))
 
    # Start traversing elements
    j = 0;
    for i in range(0, n-1):
 
        # If current element is
        # not equal to next
        # element then store that
        # current element
        if arr[i] != arr[i+1]:
            temp[j] = arr[i]
            j += 1
 
    # Store the last element
    # as whether it is unique
    # or repeated, it hasn't
    # stored previously
    temp[j] = arr[n-1]
    j += 1
     
    # Modify original array
    for i in range(0, j):
        arr[i] = temp[i]
 
    return j
 
# Driver code
arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
n = len(arr)
 
# removeDuplicates() returns
# new size of array.
n = removeDuplicates(arr, n)
 
# Print updated array
for i in range(n):
    print ("%d"%(arr[i]), end = " ")

C#

// Simple C# program to remove
// duplicates
using System;
 
class GFG {
     
    // Function to remove duplicate
    // elements This function returns
    // new size of modified array.
    static int removeDuplicates(int []arr, int n)
    {
         
        // Return, if array is empty
        // or contains a single element
        if (n == 0 || n == 1)
            return n;
     
        int []temp = new int[n];
         
        // Start traversing elements
        int j = 0;
         
        for (int i = 0; i < n - 1; i++)
         
            // If current element is not equal
            // to next element then store that
            // current element
            if (arr[i] != arr[i+1])
                temp[j++] = arr[i];
         
        // Store the last element as
        // whether it is unique or
        // repeated, it hasn't
        // stored previously
        temp[j++] = arr[n-1];
         
        // Modify original array
        for (int i = 0; i < j; i++)
            arr[i] = temp[i];
     
        return j;
    }
     
    public static void Main ()
    {
        int []arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
        int n = arr.Length;
         
        n = removeDuplicates(arr, n);
 
        // Print updated array
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}
 
// This code is contributed by nitin mittal.

Javascript

<script>
 
// Simple JavaScript program to remove
// duplicates
 
// Function to remove duplicate elements
// This function returns new size of modified
// array.
function removeDuplicates(arr, n)
{
    // Return, if array is empty
    // or contains a single element
    if (n==0 || n==1)
        return n;
 
    var temp = new Array(n);
 
    // Start traversing elements
    var j = 0;
    for (var i=0; i<n-1; i++)
 
        // If current element is not equal
        // to next element then store that
        // current element
        if (arr[i] != arr[i+1])
            temp[j++] = arr[i];
 
    // Store the last element as whether
    // it is unique or repeated, it hasn't
    // stored previously
    temp[j++] = arr[n-1];
 
    // Modify original array
    for (var i=0; i<j; i++)
        arr[i] = temp[i];
 
    return j;
}
 
var arr = [1, 2, 2, 3, 4, 4, 4, 5, 5];
    var n = arr.length;
 
    // removeDuplicates() returns new size of
    // array.
    n = removeDuplicates(arr, n);
 
    // Print updated array
    for (var i=0; i<n; i++)
       document.write( arr[i]+" ");
 
// This code is contributed by SoumikMondal
 
</script>
Producción

1 2 3 4 5 

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)

Método 2: (espacio extra constante)

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

Implementación:

C++

// C++ program to remove duplicates in-place
#include<iostream>
using namespace std;
 
// Function to remove duplicate elements
// This function returns new size of modified
// array.
int removeDuplicates(int arr[], int n)
{
    if (n==0 || n==1)
        return n;
 
    // To store index of next unique element
    int j = 0;
 
    // Doing same as done in Method 1
    // Just maintaining another updated index i.e. j
    for (int i=0; i < n-1; i++)
        if (arr[i] != arr[i+1])
            arr[j++] = arr[i];
 
    arr[j++] = arr[n-1];
 
    return j;
}
 
// Driver code
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // removeDuplicates() returns new size of
    // array.
    n = removeDuplicates(arr, n);
 
    // Print updated array
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
 
    return 0;
}

Java

// simple java program to remove
// duplicates
 
class Main
{
    // Function to remove duplicate elements
    // This function returns new size of modified
    // array.
    static int removeDuplicates(int arr[], int n)
    {
        if (n == 0 || n == 1)
            return n;
      
        // To store index of next unique element
        int j = 0;
      
        // Doing same as done in Method 1
        // Just maintaining another updated index i.e. j
        for (int i = 0; i < n-1; i++)
            if (arr[i] != arr[i+1])
                arr[j++] = arr[i];
      
        arr[j++] = arr[n-1];
      
        return j;
    }
     
    public static void main (String[] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
        int n = arr.length;
         
        n = removeDuplicates(arr, n);
  
        // Print updated array
        for (int i=0; i<n; i++)
           System.out.print(arr[i]+" ");
    }
}
 
/* This code is contributed by Harsh Agarwal */

C#

// simple C# program to remove
// duplicates
using System;
 
class GfG {
     
    // Function to remove duplicate
    // elements This function returns
    // new size of modified array.
    static int removeDuplicates(int []arr, int n)
    {
         
        if (n == 0 || n == 1)
            return n;
     
        // To store index of next
        // unique element
        int j = 0;
     
        // Doing same as done in Method 1
        // Just maintaining another updated
        // index i.e. j
        for (int i = 0; i < n - 1; i++)
            if (arr[i] != arr[i + 1])
                arr[j++] = arr[i];
     
        arr[j++] = arr[n - 1];
     
        return j;
    }
     
    public static void Main ()
    {
        int []arr = {1, 2, 2, 3, 4, 4,
                                 4, 5, 5};
        int n = arr.Length;
         
        n = removeDuplicates(arr, n);
 
        // Print updated array
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}
 
// This code is contributed by parashar.

Javascript

<script>
// simple javascript program to remove
// duplicates
 
    // Function to remove duplicate elements
    // This function returns new size of modified
    // array.
    function removeDuplicates(arr , n) {
        if (n == 0 || n == 1)
            return n;
 
        // To store index of next unique element
        var j = 0;
 
        // Doing same as done in Method 1
        // Just maintaining another updated index i.e. j
        for (i = 0; i < n - 1; i++)
            if (arr[i] != arr[i + 1])
                arr[j++] = arr[i];
 
        arr[j++] = arr[n - 1];
 
        return j;
    }
 
     
        var arr = [ 1, 2, 2, 3, 4, 4, 4, 5, 5 ];
        var n = arr.length;
 
        n = removeDuplicates(arr, n);
 
        // Print updated array
        for (i = 0; i < n; i++)
            document.write(arr[i] + " ");
 
// This code is contributed by umadevi9616
</script>
Producción

1 2 3 4 5 

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(1)

Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *