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)
- Cree una array auxiliar temp[] para almacenar elementos únicos.
- 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 .
- Copie j elementos de temp[] a arr[] y devuelva j
Implementació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