Dada una array ordenada de tamaño N , la tarea es reducir la array de modo que cada elemento pueda aparecer como máximo dos veces.
Ejemplos:
Entrada: arr[] = {1, 2, 2, 2, 3}
Salida: {1, 2, 2, 3}
Explicación:
elimine 2 una vez, ya que aparece más de 2 veces.Entrada: arr[] = {3, 3, 3}
Salida: {3, 3}
Explicación:
elimine 3 una vez, ya que aparece más de 2 veces.
Enfoque: Esto se puede resolver con la ayuda del algoritmo de dos punteros .
- Comience a recorrer la array desde la izquierda y mantenga dos punteros.
- Se usa un puntero (digamos i) para iterar la array.
- Y el segundo puntero (digamos st) avanza para encontrar el siguiente elemento único. El elemento en i aparece más de dos veces.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to reduce the array
// such that each element appears
// at most 2 times
#include <bits/stdc++.h>
using namespace std;
// Function to remove duplicates
void removeDuplicates(int arr[], int n)
{
// Initialise 2nd pointer
int st = 0;
// Iterate over the array
for (int i = 0; i < n; i++) {
if (i < n - 2
&& arr[i] == arr[i + 1]
&& arr[i] == arr[i + 2])
continue;
// Updating the 2nd pointer
else {
arr[st] = arr[i];
st++;
}
}
cout << "{";
for (int i = 0; i < st; i++) {
cout << arr[i];
if (i != st - 1)
cout << ", ";
}
cout << "}";
}
// Driver code
int main()
{
int arr[]
= { 1, 1, 1, 2,
2, 2, 3, 3,
3, 3, 3, 3,
4, 5 };
int n = sizeof(arr)
/ sizeof(arr[0]);
// Function call
removeDuplicates(arr, n);
return 0;
}
Java
// Java program to reduce the array
// such that each element appears
// at most 2 times
class GFG
{
// Function to remove duplicates
static void removeDuplicates(int arr[], int n)
{
// Initialise 2nd pointer
int st = 0;
// Iterate over the array
for (int i = 0; i < n; i++) {
if (i < n - 2
&& arr[i] == arr[i + 1]
&& arr[i] == arr[i + 2])
continue;
// Updating the 2nd pointer
else {
arr[st] = arr[i];
st++;
}
}
System.out.print("{");
for (int i = 0; i < st; i++) {
System.out.print(arr[i]);
if (i != st - 1)
System.out.print(", ");
}
System.out.print("}");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 1, 1, 2,
2, 2, 3, 3,
3, 3, 3, 3,
4, 5 };
int n = arr.length;
// Function call
removeDuplicates(arr, n);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to reduce the array
# such that each element appears
# at most 2 times
# Function to remove duplicates
def removeDuplicates(arr, n) :
# Initialise 2nd pointer
st = 0;
# Iterate over the array
for i in range(n) :
if (i < n - 2 and arr[i] == arr[i + 1]
and arr[i] == arr[i + 2]) :
continue;
# Updating the 2nd pointer
else :
arr[st] = arr[i];
st += 1;
print("{",end="")
for i in range(st) :
print(arr[i],end="");
if (i != st - 1) :
print(", ",end="");
print("}",end="");
# Driver code
if __name__ == "__main__" :
arr = [ 1, 1, 1, 2,
2, 2, 3, 3,
3, 3, 3, 3,
4, 5 ];
n = len(arr);
# Function call
removeDuplicates(arr, n);
# This code is contributed by Yash_R
C#
// C# program to reduce the array
// such that each element appears
// at most 2 times
using System;
class GFG
{
// Function to remove duplicates
static void removeDuplicates(int []arr, int n)
{
// Initialise 2nd pointer
int st = 0;
// Iterate over the array
for (int i = 0; i < n; i++) {
if (i < n - 2
&& arr[i] == arr[i + 1]
&& arr[i] == arr[i + 2])
continue;
// Updating the 2nd pointer
else {
arr[st] = arr[i];
st++;
}
}
Console.Write("{");
for (int i = 0; i < st; i++) {
Console.Write(arr[i]);
if (i != st - 1)
Console.Write(", ");
}
Console.Write("}");
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 1, 1, 2,
2, 2, 3, 3,
3, 3, 3, 3,
4, 5 };
int n = arr.Length;
// Function call
removeDuplicates(arr, n);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Java program to reduce the array
// such that each element appears
// at most 2 times
// Function to remove duplicates
function removeDuplicates(arr,n)
{
// Initialise 2nd pointer
let st = 0;
// Iterate over the array
for (let i = 0; i < n; i++) {
if (i < n - 2
&& arr[i] == arr[i + 1]
&& arr[i] == arr[i + 2])
continue;
// Updating the 2nd pointer
else {
arr[st] = arr[i];
st++;
}
}
document.write("{");
for (let i = 0; i < st; i++) {
document.write(arr[i]);
if (i != st - 1)
document.write(", ");
}
document.write("}");
}
// Driver code
let arr = [ 1, 1, 1, 2,
2, 2, 3, 3,
3, 3, 3, 3,
4, 5 ];
let n = arr.length;
// Function call
removeDuplicates(arr, n);
// This code is contributed by sravan kumar
</script>
Producción
{1, 1, 2, 2, 3, 3, 4, 5}
Complejidad temporal: O(N)
Complejidad espacial: O(1)
Otro enfoque: usar la función Counter()
- Calcule la frecuencia de todos los elementos utilizando una función de contador.
- Tome una lista vacía.
- Atraviesa la array.
- Si la frecuencia de cualquier elemento es mayor o igual a 2, haga que su frecuencia sea 1 y agréguelo a la lista.
- Si la frecuencia de cualquier elemento es igual a 1, tome su frecuencia 0 y agréguela a la lista.
- Imprime la lista.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python3 program to reduce the array # such that each element appears # at most 2 times from collections import Counter # Function to remove duplicates def removeDuplicates(arr, n): freq = Counter(arr) # Taking empty list l = [] for i in range(n): if(freq[arr[i]] >= 2): # Making frequency to 1 freq[arr[i]] = 1 l.append(arr[i]) elif(freq[arr[i]] == 1): # Making frequency to 0 # and appending to list l.append(arr[i]) freq[arr[i]] = 0 # Printing the list for i in l: print(i, end=" ") # Driver code if __name__ == "__main__": arr = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5] n = len(arr) # Function call removeDuplicates(arr, n) # This code is contributed by vikkycirus
Producción
1 1 2 2 3 3 4 5
Complejidad del tiempo: O(N)
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA