Imp Dada una array de números primos tal que el rango de números primos es pequeño. Eliminar duplicados de la array.
Ejemplos:
Input: arr[] = {3, 5, 7, 2, 2, 5, 7, 7};
Output: arr[] = {2, 3, 5, 7}
All the duplicates are removed from
the array. The output can be printed in any order.
Input: arr[] = {3, 5, 7, 3, 3, 13, 5, 13, 29, 13};
Output: arr[] = {3, 5, 7, 13, 29}
All the duplicates are removed from
the array. The output can be printed in any order.
Fuente: pregunta de la entrevista de Amazon
Método 1 : Este método analiza el enfoque ingenuo que tomauna complejidad de tiempo O(n 2 ).
Enfoque: Entonces, la idea básica es verificar cada elemento, ya sea que haya ocurrido previamente o no. Por lo tanto, el enfoque implica mantener dos bucles, uno para seleccionar el elemento o índice actual y el bucle interno para comprobar si el elemento se ha producido previamente o no.
Algoritmo:
- Comience ejecutando dos bucles.
- Elija todos los elementos uno por uno.
- Para cada elemento seleccionado, verifique si ya ocurrió o no.
- Si ya lo vio, ignórelo, de lo contrario, agréguelo a la array.
Implementación:
C++
// A C++ program to implement Naive
// approach to remove duplicates.
#include <bits/stdc++.h>
using namespace std;
int removeDups(vector<int>& vect)
{
int res_ind = 1;
// Loop invariant: Elements from vect[0]
// to vect[res_ind-1] are unique.
for (int i = 1; i < vect.size(); i++) {
int j;
for (j = 0; j < i; j++)
if (vect[i] == vect[j])
break;
if (j == i)
vect[res_ind++] = vect[i];
}
// Removes elements from vect[res_ind] to
// vect[end]
vect.erase(vect.begin() + res_ind, vect.end());
}
// Driver code
int main()
{
vector<int> vect{ 3, 5, 7, 2, 2, 5, 7, 7 };
removeDups(vect);
for (int i = 0; i < vect.size(); i++)
cout << vect[i] << " ";
return 0;
}
Java
// Java program to implement Naive
// approach to remove duplicates
class GFG {
static int[] removeDups(int[] vect)
{
int res_ind = 1;
// Loop invariant: Elements from vect[0]
// to vect[res_ind-1] are unique.
for (int i = 1; i < vect.length; i++) {
int j;
for (j = 0; j < i; j++)
if (vect[i] == vect[j])
break;
if (j == i)
vect[res_ind++] = vect[i];
}
// Removes elements from vect[res_ind]
// to vect[end]
int[] new_arr = new int[res_ind];
for (int i = 0; i < res_ind; i++)
new_arr[i] = vect[i];
return new_arr;
}
// Driver Code
public static void main(String[] args)
{
int[] vect = { 3, 5, 7, 2, 2, 5, 7, 7 };
vect = removeDups(vect);
for (int i = 0; i < vect.length; i++)
System.out.print(vect[i] + " ");
System.out.println();
}
}
// This code is contributed by
// sanjeev2552
Python3
# A Python3 program to implement # Naive approach to remove duplicates. def removeDups(vect): res_ind = 1 # Loop invariant : Elements from vect[0] # to vect[res_ind-1] are unique. for i in range(1, len(vect)): j = 0 while (j < i): if (vect[i] == vect[j]): break j += 1 if (j == i): vect[res_ind] = vect[i] res_ind += 1 # Removes elements from # vect[res_ind] to vect[end] return vect[0:res_ind] # Driver code vect = [3, 5, 7, 2, 2, 5, 7, 7] vect = removeDups(vect) for i in range(len(vect)): print(vect[i], end = " ") # This code is contributed # by mohit kumar
C#
// C# program to implement Naive approach
// to remove duplicates
using System;
class GFG {
static int[] removeDups(int[] vect)
{
int res_ind = 1;
// Loop invariant : Elements from vect[0]
// to vect[res_ind-1] are unique.
for (int i = 1; i < vect.Length; i++) {
int j;
for (j = 0; j < i; j++)
if (vect[i] == vect[j])
break;
if (j == i)
vect[res_ind++] = vect[i];
}
// Removes elements from vect[res_ind]
// to vect[end]
int[] new_arr = new int[res_ind];
for (int i = 0; i < res_ind; i++)
new_arr[i] = vect[i];
return new_arr;
}
// Driver Code
public static void Main(String[] args)
{
int[] vect = { 3, 5, 7, 2, 2, 5, 7, 7 };
vect = removeDups(vect);
for (int i = 0; i < vect.Length; i++)
Console.Write(vect[i] + " ");
Console.WriteLine();
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement Naive
// approach to remove duplicates
function removeDups(vect)
{
let res_ind = 1;
// Loop invariant: Elements from vect[0]
// to vect[res_ind-1] are unique.
for (let i = 1; i < vect.length; i++) {
let j;
for (j = 0; j < i; j++)
if (vect[i] == vect[j])
break;
if (j == i)
vect[res_ind++] = vect[i];
}
// Removes elements from vect[res_ind]
// to vect[end]
let new_arr = new Array(res_ind);
for (let i = 0; i < res_ind; i++)
new_arr[i] = vect[i];
return new_arr;
}
// Driver Code
let vect=[3, 5, 7, 2, 2, 5, 7, 7];
vect = removeDups(vect);
for (let i = 0; i < vect.length; i++)
document.write(vect[i] + " ");
document.write("<br>");
// This code is contributed by unknown2108
</script>
Producción
3 5 7 2
Análisis de Complejidad:
- Complejidad Temporal: O(n 2 ).
Como se utilizan dos bucles anidados, la complejidad del tiempo se convierte en O(n 2 ). - Complejidad espacial: O(n).
Como se utiliza una array adicional para almacenar los elementos, la complejidad del espacio es O(n).
Método 2 : este método implica la técnica de clasificación que requiere un tiempo O (n log n).
Enfoque: en comparación con el enfoque anterior, una mejor solución es ordenar primero la array y luego eliminar todos los elementos adyacentes que son similares de la array ordenada.
Algoritmo:
- Primero ordena la array.
- La necesidad de espacio adicional se puede evitar inteligentemente. Manteniendo dos variables, la primera = 1 y la i = 1.
- Atraviesa la array desde el segundo elemento hasta el final.
- Para cada elemento, si ese elemento no es igual al elemento anterior, entonces array[first++] = array[i] , donde i es el contador de un ciclo.
- Entonces, la longitud de la array sin duplicados es primero , elimine los elementos restantes.
Nota: En CPP hay algunas funciones integradas como sort() para ordenar y unique() para eliminar duplicados adyacentes. La función unique() pone todos los elementos únicos al principio y devuelve un iterador que apunta al primer elemento después del elemento único. La función erase() elimina elementos entre dos iteradores dados.
Implementación:
C++
// C++ program to remove duplicates using Sorting
#include <bits/stdc++.h>
using namespace std;
int removeDups(vector<int>& vect)
{
// Sort the vector
sort(vect.begin(), vect.end());
// unique() removes adjacent duplicates.
// unique function puts all unique elements at
// the beginning and returns iterator pointing
// to the first element after unique element.
// Erase function removes elements between two
// given iterators
vect.erase(unique(vect.begin(), vect.end()),
vect.end());
}
// Driver code
int main()
{
vector<int> vect{ 3, 5, 7, 2, 2, 5, 7, 7 };
removeDups(vect);
for (int i = 0; i < vect.size(); i++)
cout << vect[i] << " ";
return 0;
}
Java
// Java program to remove duplicates using Sorting
import java.util.*;
class GFG {
static int[] removeDups(int[] vect)
{
// sort the array
Arrays.sort(vect);
// pointer
int first = 1;
// remove duplicate elements
for (int i = 1; i < vect.length; i++)
if (vect[i] != vect[i - 1])
vect[first++] = vect[i];
// mark rest of elements to INT_MAX
for (int i = first; i < vect.length; i++)
vect[i] = Integer.MAX_VALUE;
return vect;
}
// Driver code
public static void main(String[] args)
{
int[] vect = { 3, 5, 7, 2, 2, 5, 7, 7 };
vect = removeDups(vect);
for (int i = 0; i < vect.length; i++) {
if (vect[i] == Integer.MAX_VALUE)
break;
System.out.print(vect[i] + " ");
}
}
}
Python3
# Python3 program to remove duplicates # using Sorting import sys def removeDups(vect): # Sort the array vect.sort() # Pointer first = 1 # Remove duplicate elements for i in range(1, len(vect)): if (vect[i] != vect[i - 1]): vect[first] = vect[i] first += 1 # Mark rest of elements to INT_MAX for i in range(first, len(vect)): vect[i] = sys.maxsize return vect # Driver code vect = [ 3, 5, 7, 2, 2, 5, 7, 7 ] vect = removeDups(vect) for i in range(len(vect)): if (vect[i] == sys.maxsize): break print(vect[i], end = " ") # This code is contributed by avanitrachhadiya2155
C#
// C# program to remove duplicates using Sorting
using System;
class GFG
{
static int[] removeDups(int[] vect)
{
// sort the array
Array.Sort(vect);
// pointer
int first = 1;
// remove duplicate elements
for (int i = 1; i < vect.Length; i++)
if (vect[i] != vect[i - 1])
vect[first++] = vect[i];
// mark rest of elements to INT_MAX
for (int i = first; i < vect.Length; i++)
vect[i] = int.MaxValue;
return vect;
}
// Driver code
public static void Main(params string[] args)
{
int[] vect = { 3, 5, 7, 2, 2, 5, 7, 7 };
vect = removeDups(vect);
for (int i = 0; i < vect.Length; i++)
{
if (vect[i] == int.MaxValue)
break;
Console.Write(vect[i] + " ");
}
}
}
// This code is contributed by rutvik_56.
Javascript
<script>
// Javascript program to remove duplicates using Sorting
function removeDups(vect) {
// Sort the vector
vect.sort((a, b) => a - b)
// pointer
let first = 1;
// remove duplicate elements
for (let i = 1; i < vect.length; i++){
if (vect[i] != vect[i - 1])
vect[first++] = vect[i];
}
// mark rest of elements to INT_MAX
for (let i = first; i < vect.length; i++)
vect[i] = Number.MAX_SAFE_INTEGER;
return vect;
}
// Driver code
let vect = [ 3, 5, 7, 2, 2, 5, 7, 7 ];
removeDups(vect);
for (let i = 0; i < vect.length; i++) {
if (vect[i] == Number.MAX_SAFE_INTEGER)
break;
document.write(vect[i] + " ");
}
</script>
Producción
2 3 5 7
Producción:
Análisis de Complejidad:
- Complejidad Temporal: O(n Log n).
Para ordenar la array O(n log n ) se requiere complejidad de tiempo, y para eliminar elementos adyacentes se requiere O(n) complejidad de tiempo. - Espacio auxiliar: O(1)
Como no se requiere espacio extra, la complejidad del espacio es constante.
Método 3 : El método implica la técnica de Hashing, que requiere O(n) tiempo.
Enfoque: la complejidad del tiempo en este método se puede reducir, pero la complejidad del espacio tendrá un costo. Esto implica el uso de Hashing donde los números se marcan en un HashMap, de modo que si se vuelve a encontrar el número, se borre de la array.
Algoritmo:
- Utilice un conjunto de hash. HashSet almacena solo elementos únicos.
- Se sabe que si se colocan dos de los mismos elementos en un HashSet, el HashSet almacena solo un elemento (todos los elementos duplicados desaparecen)
- Atraviesa la array de principio a fin.
- Para cada elemento, inserte el elemento en el HashSet
- Ahora recorra el HashSet y coloque los elementos en el HashSet en la array
Implementación:
C++
// C++ program to remove duplicates using Hashing
#include <bits/stdc++.h>
using namespace std;
int removeDups(vector<int>& vect)
{
// Create a set from vector elements
unordered_set<int> s(vect.begin(), vect.end());
// Take elements from set and put back in
// vect[]
vect.assign(s.begin(), s.end());
}
// Driver code
int main()
{
vector<int> vect{ 3, 5, 7, 2, 2, 5, 7, 7 };
removeDups(vect);
for (int i = 0; i < vect.size(); i++)
cout << vect[i] << " ";
return 0;
}
Java
// Java program to implement Naive approach to
// remove duplicates.
import java.util.*;
class GFG {
static void removeDups(Vector<Integer> vect)
{
// Create a set from vector elements
Set<Integer> set = new HashSet<Integer>(vect);
// Take elements from set and put back in
// vect[]
vect.clear();
vect.addAll(set);
}
// Driver code
public static void main(String[] args)
{
Integer arr[] = { 3, 5, 7, 2, 2, 5, 7, 7 };
Vector<Integer> vect
= new Vector<Integer>(
Arrays.asList(arr));
removeDups(vect);
for (int i = 0; i < vect.size(); i++) {
System.out.print(vect.get(i) + " ");
}
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 program to remove duplicates using Hashing def removeDups(): global vect # Create a set from vector elements s = set(vect) # Take elements from set and put back in # vect[] vect = s # Driver code vect = [3, 5, 7, 2, 2, 5, 7, 7] removeDups() for i in vect: print(i, end = " ") # This code is contributed by shubhamsingh10
C#
// C# program to implement Naive approach to
// remove duplicates.
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
static List<int> removeDups(List<int> vect)
{
// Create a set from vector elements
HashSet<int> set = new HashSet<int>(vect);
// Take elements from set and put back in
// vect[]
vect.Clear();
vect = set.ToList();
return vect;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 3, 5, 7, 2, 2, 5, 7, 7 };
List<int> vect = new List<int>(arr);
vect = removeDups(vect);
for (int i = 0; i < vect.Count; i++) {
Console.Write(vect[i] + " ");
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to implement Naive approach to
// remove duplicates.
function removeDups(vect)
{
// Create a set from vector elements
letset = new Set(vect);
// Take elements from set and put back in
// vect[]
vect=[];
vect=Array.from(letset);
return vect;
}
// Driver code
let vect=[3, 5, 7, 2, 2, 5, 7, 7 ];
vect=removeDups(vect);
for (let i = 0; i < vect.length; i++) {
document.write(vect[i] + " ");
}
// This code is contributed by rag2127
</script>
Producción
2 7 5 3
Análisis de Complejidad:
- Complejidad temporal: O(n).
Dado que se necesita un solo recorrido para ingresar todos los elementos en el mapa hash, la complejidad del tiempo es O(n) . - Espacio Auxiliar: O(n).
Para almacenar elementos en HashSet o hashmap O(n) se necesita complejidad espacial.
Método 4 : se enfoca en valores de rango pequeño donde la complejidad del tiempo es O(n).
Enfoque: este enfoque solo funciona cuando el producto de todos los primos distintos es menor que 10^18 y todos los números de la array deben ser primos. La propiedad de los primos de no tener divisores excepto 1 o ese mismo número se usa para llegar a la solución. A medida que los elementos de la array se eliminan de la array, mantienen un valor (producto) que contendrá el producto de todos los números primos distintos encontrados previamente en la array, de modo que si el elemento divide el producto, pueden estar seguros de que el elemento tiene ocurrió anteriormente en la array y, por lo tanto, el número será rechazado.
Algoritmo:
- Inicialmente, mantenga una variable (p = 1).
- Atraviesa la array de principio a fin.
- Mientras se desplaza, compruebe si p es divisible por el i-ésimo elemento. Si es cierto, entonces borre ese elemento.
- De lo contrario, mantenga ese elemento y actualice el producto multiplicando ese elemento con el producto (p = p * arr[i])
Implementación:
C++
// Removes duplicates using multiplication of
// distinct primes in array
#include <bits/stdc++.h>
using namespace std;
int removeDups(vector<int>& vect)
{
long long int prod = vect[0];
int res_ind = 1;
for (int i = 1; i < vect.size(); i++) {
if (prod % vect[i] != 0) {
vect[res_ind++] = vect[i];
prod *= vect[i];
}
}
vect.erase(vect.begin() + res_ind, vect.end());
}
// Driver code
int main()
{
vector<int> vect{ 3, 5, 7, 2, 2, 5, 7, 7 };
removeDups(vect);
for (int i = 0; i < vect.size(); i++)
cout << vect[i] << " ";
return 0;
}
Java
// Removes duplicates using multiplication of
// distinct primes in array
import java.util.*;
class GFG {
static int[] removeDups(int[] vect)
{
int prod = vect[0];
int res_ind = 1;
for (int i = 1; i < vect.length; i++) {
if (prod % vect[i] != 0) {
vect[res_ind++] = vect[i];
prod *= vect[i];
}
}
return Arrays.copyOf(vect, res_ind);
}
// Driver code
public static void main(String[] args)
{
int[] vect = { 3, 5, 7, 2, 2, 5, 7, 7 };
vect = removeDups(vect);
for (int i = 0; i < vect.length; i++)
System.out.print(vect[i] + " ");
}
}
// This code is contributed by 29AjayKumar
Python3
# Removes duplicates using multiplication of # distinct primes in array def removeDups(vect): prod = vect[0] res_ind = 1 i = 1 while (i < len(vect)): if (prod % vect[i] != 0): vect[res_ind] = vect[i] res_ind += 1 prod *= vect[i] vect = vect[:res_ind + 2] i += 1 return vect # Driver code vect = [3, 5, 7, 2, 2, 5, 7, 7] vect = removeDups(vect) for i in range(len(vect)): print(vect[i], end =" ") # This code is contributed by SHUBHAMSINGH10
C#
// Removes duplicates using multiplication of
// distinct primes in array
using System;
class GFG {
static int[] removeDups(int[] vect)
{
int prod = vect[0];
int res_ind = 1;
for (int i = 1; i < vect.Length; i++) {
if (prod % vect[i] != 0) {
vect[res_ind++] = vect[i];
prod *= vect[i];
}
}
int[] temp = new int[vect.Length - res_ind];
Array.Copy(vect, 0, temp, 0, temp.Length);
return temp;
}
// Driver code
public static void Main(String[] args)
{
int[] vect = { 3, 5, 7, 2, 2, 5, 7, 7 };
vect = removeDups(vect);
for (int i = 0; i < vect.Length; i++)
Console.Write(vect[i] + " ");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Removes duplicates using multiplication of
// distinct primes in array
function removeDups(vect)
{
let prod = vect[0];
let res_ind = 1;
for (let i = 1; i < vect.length; i++) {
if (prod % vect[i] != 0) {
vect[res_ind++] = vect[i];
prod *= vect[i];
vect=vect.slice(0,res_ind + 2);
}
}
return vect;
}
// Driver code
let vect=[3, 5, 7, 2, 2, 5, 7, 7];
vect = removeDups(vect);
document.write(vect.join(" "));
// This code is contributed by rag2127
</script>
Producción
3 5 7 2
Análisis de Complejidad:
- Complejidad temporal: O(n).
Para recorrer la array solo una vez, el tiempo requerido es O(n) . - Espacio Auxiliar: O(1).
Se necesita una variable p, por lo que la complejidad del espacio es constante.
Nota: esta solución no funcionaría si hay compuestos en la array.
Este artículo es una contribución de Shivam Mittal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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