Array eliminar elementos duplicados

Tengo una matriz sin clasificar, ¿cuál es el mejor método para eliminar todos los duplicados de un elemento si está presente?

p.ej:

a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3] 

entonces después de esa operación la matriz debería verse como

  a[1,5,2,6,8,9,10,3,4,11] 

Verifica cada elemento contra cualquier otro elemento

La solución ingenua es verificar cada elemento contra cualquier otro elemento. Esto es un desperdicio y produce una solución O (n 2 ), incluso si solo avanzas “hacia adelante”.

Ordenar y eliminar duplicados

Una mejor solución es ordenar la matriz y luego verificar cada elemento con el siguiente para encontrar duplicados. Elija un tipo eficiente y este es O (n log n).

La desventaja de la solución basada en la clasificación es que el orden no se mantiene. Sin embargo, un paso adicional puede solucionarlo. Coloque todas las entradas (en la única matriz ordenada) en una tabla hash, que tiene acceso O (1). Luego itera sobre la matriz original. Para cada elemento, verifique si está en la tabla hash. Si es así, agréguelo al resultado y elimínelo de la tabla hash. Usted terminará con una matriz resultante que tiene el orden del original, con cada elemento en la misma posición que su primera aparición.

Tipos lineales de enteros

Si está trabajando con enteros de un rango fijo, puede hacerlo aún mejor utilizando una ordenación de radix. Si supone que los números están todos en el rango de 0 a 1,000,000, por ejemplo, puede asignar un vector de bits de aproximadamente 1,000,001. Para cada elemento en la matriz original, establece el bit correspondiente en función de su valor (por ejemplo, un valor de 13 resultados al establecer el 14º bit). Luego recorra la matriz original, verifique si está en el vector de bits. Si es así, agrégalo a la matriz de resultados y borra ese bit del vector de bits. Esto es O (n) y intercambia espacio por tiempo.

Solución de tabla hash

Lo que nos lleva a la mejor solución de todas: el género es en realidad una distracción, aunque útil. Cree una tabla hash con acceso O (1). Atraviesa la lista original. Si ya no está en la tabla hash, agréguela a la matriz resultante y agréguela a la tabla hash. Si está en la tabla hash, ignórelo.

Esta es de lejos la mejor solución. Entonces, ¿por qué el rest? Debido a problemas como este, se trata de adaptar el conocimiento que tiene (o debería tener) a los problemas y refinarlos en función de las suposiciones que se convierten en una solución. Desarrollar una solución y comprender el pensamiento detrás de esto es mucho más útil que regurgitar una solución.

Además, las tablas hash no siempre están disponibles. Tome un sistema integrado o algo donde el espacio sea MUY limitado. Puede implementar una ordenación rápida en un puñado de códigos de operación, mucho menos que cualquier tabla hash.

Esto se puede hacer en O (n) amortizado usando un conjunto basado en hashtable.

Código Psuedo:

 s := new HashSet c := 0 for each el in a Add el to s. If el was not already in s, move (copy) el c positions left. If it was in s, increment c. 

Si no necesita conservar el objeto original, puede crear un bucle y crear una nueva matriz de valores únicos. En C # use una lista para acceder a la funcionalidad requerida. No es la solución más atractiva o inteligente, pero funciona.

 int[] numbers = new int[] {1,2,3,4,5,1,2,2,2,3,4,5,5,5,5,4,3,2,3,4,5}; List unique = new List(); foreach (int i in numbers) if (!unique.Contains(i)) unique.Add(i); unique.Sort(); numbers = unique.ToArray(); 

Trata los números como llaves.

 for each elem in array: if hash(elem) == 1 //duplicate ignore it next else hash(elem) = 1 add this to resulting array end 

Si conoce los datos como el rango de números y si es finito, entonces puede inicializar esa gran matriz con ZERO.

 array flag[N] //N is the max number in the array for each elem in input array: if flag[elem - 1] == 0 flag[elem - 1] = 1 add it to resulatant array else discard it //duplicate end 

  indexOutput = 1; outputArray[0] = arrayInt[0]; int j; for (int i = 1; i < arrayInt.length; i++) { j = 0; while ((outputArray[j] != arrayInt[i]) && j < indexOutput) { j++; } if(j == indexOutput){ outputArray[indexOutput] = arrayInt[i]; indexOutput++; } } 

Use una implementación de conjunto.
HashSet , TreeSet o LinkedHashSet si es Java.

Estoy de acuerdo con Cletus. Usa una QuickSort y luego elimina dups

Este es un segmento de código que creé en C ++, Pruébalo

 #include  using namespace std; int main() { cout << " Delete the duplicate" << endl; int numberOfLoop = 10; int loopCount =0; int indexOfLargeNumber = 0; int largeValue = 0; int indexOutput = 1; //Array to hold the numbers int arrayInt[10] = {}; int outputArray [10] = {}; // Loop for reading the numbers from the user input while(loopCount < numberOfLoop){ cout << "Please enter one Integer number" << endl; cin >> arrayInt[loopCount]; loopCount = loopCount + 1; } outputArray[0] = arrayInt[0]; int j; for (int i = 1; i < numberOfLoop; i++) { j = 0; while ((outputArray[j] != arrayInt[i]) && j < indexOutput) { j++; } if(j == indexOutput){ outputArray[indexOutput] = arrayInt[i]; indexOutput++; } } cout << "Printing the Non duplicate array"<< endl; //Reset the loop count loopCount =0; while(loopCount < numberOfLoop){ if(outputArray[loopCount] != 0){ cout << outputArray[loopCount] << endl; } loopCount = loopCount + 1; } return 0; } 

Mi solución ( O(N) ) no usa memoria adicional, pero la matriz debe haber sido ordenada (mi clase usa el algoritmo de ordenación de inserción, pero no importa):

  public class MyArray { //data arr private int[] _arr; //field length of my arr private int _leght; //counter of duplicate private int countOfDup = 0; //property length of my arr public int Length { get { return _leght; } } //constructor public MyArray(int n) { _arr = new int[n]; _leght = 0; } // put element into array public void Insert(int value) { _arr[_leght] = value; _leght++; } //Display array public void Display() { for (int i = 0; i < _leght; i++) Console.Out.Write(_arr[i] + " "); } //Insertion sort for sorting array public void InsertSort() { int t, j; for (int i = 1; i < _leght; i++) { t = _arr[i]; for (j = i; j > 0; ) { if (_arr[j - 1] >= t) { _arr[j] = _arr[j - 1]; j--; } else break; } _arr[j] = t; } } private void _markDuplicate() { //mark duplicate Int32.MinValue for (int i = 0; i < _leght - 1; i++) { if (_arr[i] == _arr[i + 1]) { countOfDup++; _arr[i] = Int32.MinValue; } } } //remove duplicates O(N) ~ O(2N) ~ O(N + N) public void RemoveDups() { _markDuplicate(); if (countOfDup == 0) return; //no duplicate int temp = 0; for (int i = 0; i < _leght; i++) { // if duplicate remember and continue if (_arr[i] == Int32.MinValue) continue; else //else need move { if (temp != i) _arr[temp] = _arr[i]; temp++; } } _leght -= countOfDup; } } 

Y principal

 static void Main(string[] args) { Random r = new Random(DateTime.Now.Millisecond); int i = 11; MyArray a = new MyArray(i); for (int j = 0; j < i; j++) { a.Insert(r.Next(i - 1)); } a.Display(); Console.Out.WriteLine(); a.InsertSort(); a.Display(); Console.Out.WriteLine(); a.RemoveDups(); a.Display(); Console.ReadKey(); } 
 import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Set; public class testing { public static void main(String[] args) { EligibleOffer efg = new EligibleOffer(); efg.setCode("1234"); efg.setName("hey"); EligibleOffer efg1 = new EligibleOffer(); efg1.setCode("1234"); efg1.setName("hey1"); EligibleOffer efg2 = new EligibleOffer(); efg2.setCode("1235"); efg2.setName("hey"); EligibleOffer efg3 = new EligibleOffer(); efg3.setCode("1235"); efg3.setName("hey"); EligibleOffer[] eligibleOffer = { efg, efg1,efg2 ,efg3}; removeDupliacte(eligibleOffer); } public static EligibleOffer[] removeDupliacte(EligibleOffer[] array) { List list = Arrays.asList(array); List list1 = new ArrayList(); int len = list.size(); for (int i = 0; i <= len-1; i++) { boolean isDupliacte = false; EligibleOffer eOfr = (EligibleOffer) list.get(i); String value = eOfr.getCode().concat(eOfr.getName()); if (list1.isEmpty()) { list1.add(list.get(i)); continue; } int len1 = list1.size(); for (int j = 0; j <= len1-1; j++) { EligibleOffer eOfr1 = (EligibleOffer) list1.get(j); String value1 = eOfr1.getCode().concat(eOfr1.getName()); if (value.equals(value1)) { isDupliacte = true; break; } System.out.println(value+"\t"+value1); } if (!isDupliacte) { list1.add(eOfr); } } System.out.println(list1); EligibleOffer[] eligibleOffer = new EligibleOffer[list1.size()]; list1.toArray(eligibleOffer); return eligibleOffer; } } 
 Time O(n) space O(n) #include  #include using namespace std; void fun(int arr[],int size){ int count=0; int has[100]={0}; for(int i=0;i 
 public class RemoveDuplicateArray { public static void main(String[] args) { int arr[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 2, 3, 4, 9 }; int size = arr.length; for (int i = 0; i < size; i++) { for (int j = i+1; j < size; j++) { if (arr[i] == arr[j]) { while (j < (size) - 1) { arr[j] = arr[j + 1]; j++; } size--; } } } for (int i = 0; i < size; i++) { System.out.print(arr[i] + " "); } } } 

salida - 1 2 3 4 5 6 7 9

Puede usar la syntax “in” y “not in” en python, lo que lo hace bastante directo.

La complejidad es más alta que el enfoque de hash, ya que un “no en” es equivalente a un recorrido lineal para averiguar si esa entrada existe o no.

 li = map(int, raw_input().split(",")) a = [] for i in li: if i not in a: a.append(i) print a