Encuentra duplicados en una matriz

Dado un conjunto de n elementos enteros, ¿cómo va a encontrar si hay duplicados en la matriz en el tiempo O (n) sin utilizar ningún espacio extra.

Con espacio extra, significa espacio extra de orden O (n).

¿El operador Xor ayuda de alguna manera?

Si no hay información adicional, esta pregunta parece ser incobrable, ya que este es el Problema de distinción de elementos , que no puede resolverse con las restricciones que usted proporcionó, en el tiempo requerido.

puedes permitir:

(1) más memoria y use un hashtable / hashset y cumpla con los criterios de tiempo O (n). [iterar la matriz, verificar si un elemento está en la tabla hash, si es que tiene engaños, de lo contrario, inserte el elemento en la tabla y continúe].

(2) más tiempo , clasifique la matriz [O (nlogn)] y cumpla los criterios de espacio sublineal. [Después de ordenar, itere sobre la matriz, y para cada a[i] , a[i+1] , verifique si son idénticos. Si no encontró un par idéntico, no tiene engaños]

EDITAR : La prueba para este reclamo es un poco larga, y necesita notación matemática que no se admite aquí (nota al margen: realmente necesitamos soporte de tex), pero la idea es si modelamos nuestro problema como un árbol de cálculo algebraico (que es una feria asunción cuando no se permite hash, y espacio constante en la eliminación), entonces, Ben O demostró en su artículo Lower Bounds For Algebraic Computation Trees (1983) (publicado en ACM Omega(nlogn) , que la distinción de elemento es un problema de Omega(nlogn) modelo. Lubiw demostró que la misma conclusión también se aplica cuando nos limitamos a números enteros en 1991: Un límite inferior para el problema de distinción de elementos enteros , pero estos artículos concluyen que bajo el modelo de cálculo de árbol algebraico: el problema de distinción de enteros es un problema de Omega (nlogn) .

Radix Sort in situ seguido de Linear Scan

En lugar de algoritmo de ordenación de radix

Dependiendo de lo que realmente considere la complejidad de tiempo de un género Radix, esta solución es O (N) tiempo, aunque mi opinión personal no es así. Creo que si no hace la suposición de tiempo lineal en el género entero, entonces el problema no tiene solución.

Debido a que el ordenamiento está en su lugar, solo se requiere O (1) almacenamiento adicional.

El código es todo C ++ 11

Paso 1: Radix Ordenar en el lugar

 template::value>::type* = nullptr> void RecurseOnRadixSort(std::vector& myArray, T mask, int zerosEnd, int onesBegin) { if (zerosEnd+1 >= onesBegin-1 || mask == 0) return; int zerosEnd2 = zerosEnd; int onesBegin2 = onesBegin; while(zerosEnd2+1 <= onesBegin2-1) { // swap ones to the right if ((myArray[zerosEnd2+1] & mask) != 0) { std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]); --onesBegin2; } else ++zerosEnd2; } mask >>= 1; //recurse on lhs RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin); } template ::value>::type* = nullptr> void InPlaceRadixSort(std::vector& myArray) { int zerosEnd = -1; int onesBegin = static_cast(myArray.size()); T mask = static_cast(1) << sizeof(T)*8-1; while(zerosEnd+1 <= onesBegin-1) { if ( (myArray[zerosEnd+1] & mask) != 0) { std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]); --onesBegin; } else ++zerosEnd; } mask = static_cast(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype //recurse on lhs RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast(myArray.size())); // swap negatives to the front auto iterSmallest = std::min_element(myArray.begin(), myArray.end()); if (*iterSmallest < 0) { std::reverse(myArray.begin(), myArray.end()); iterSmallest = std::min_element(myArray.begin(), myArray.end()); std::reverse(myArray.begin(), iterSmallest+1); std::reverse(iterSmallest+1, myArray.end()); } } 

Paso 2: escaneo lineal para elementos duplicados

 for (size_t i=0, j=1; j 

Código completo

 #include  #include  #include  #include  #include  #include  #include  #include  using namespace std; #define N 10 template  void PrintArray(const std::vector& myArray) { for (auto&& element : myArray) { std::cout << element << std::endl; } } template::value>::type* = nullptr> void RecurseOnRadixSort(std::vector& myArray, T mask, int zerosEnd, int onesBegin) { if (zerosEnd+1 >= onesBegin-1 || mask == 0) return; int zerosEnd2 = zerosEnd; int onesBegin2 = onesBegin; while(zerosEnd2+1 <= onesBegin2-1) { // swap ones to the right if ((myArray[zerosEnd2+1] & mask) != 0) { std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]); --onesBegin2; } else ++zerosEnd2; } mask >>= 1; //recurse on lhs RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin); } template ::value>::type* = nullptr> void InPlaceRadixSort(std::vector& myArray) { int zerosEnd = -1; int onesBegin = static_cast(myArray.size()); T mask = static_cast(1) << sizeof(T)*8-1; while(zerosEnd+1 <= onesBegin-1) { if ( (myArray[zerosEnd+1] & mask) != 0) { std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]); --onesBegin; } else ++zerosEnd; } mask = static_cast(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype //recurse on lhs RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1); //recurse on rhs RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast(myArray.size())); // swap negatives to the front auto iterSmallest = std::min_element(myArray.begin(), myArray.end()); if (*iterSmallest < 0) { std::reverse(myArray.begin(), myArray.end()); iterSmallest = std::min_element(myArray.begin(), myArray.end()); std::reverse(myArray.begin(), iterSmallest+1); std::reverse(iterSmallest+1, myArray.end()); } } int main() { srand(time(NULL)); std::vector myArray(N); for (size_t i=0;i 

Demo en vivo

Aquí hay una solución interesante a este problema con una única restricción: los elementos deben estar en el rango de 0 a n-2 (inclusive) donde n es el número de elementos.

Esto funciona en O (n) tiempo con una complejidad de espacio O (1).

¡Aquí hay una solución con O (n) uso de tiempo y O (1) uso de espacio!

 Traverse the array. Do following for every index i of A[]. { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // ie, A[abs(A[i])] is negative this element (ith element of list) is a repetition } 

Créditos: Método 5 Geek para geeks

Esta solución se basa en una que elimina los duplicados de una matriz por @dsimcha, como se puede encontrar aquí .

Realiza un algoritmo de intercambio in situ, con valores hash de valor utilizados para intercambiar posiciones. Tenga en cuenta que esto destruye el contenido de la matriz original en cierta medida. Pero no había ningún requisito en la pregunta de OP que lo prohibiera.

 public static class DupFinder { public static bool HasDups(int[] array, ref int nEvals) { nEvals = 0; return DupFinder.FindInPlace(array, 0, ref nEvals); } private static bool FindInPlace(int[] array, int start, ref int nEvals) { if (array.Length - start < 2) return false; var sentinel = array[start]; var offset = start + 1; var len = array.Length - offset; for (var ndx = 0; ndx < len; nEvals++) { var cur = array[offset + ndx]; if (cur == sentinel) { ndx++; continue; } var hash = cur % len; if (ndx == hash) { ndx++; continue; } var at_hash = array[offset + hash]; if (cur == at_hash) { array[offset + ndx] = sentinel; ndx++; continue; } if (at_hash == sentinel) { Swap(array, offset, ndx, hash); ndx++; continue; } var hash_hash = at_hash % len; if (hash_hash != hash) { Swap(array, offset, ndx, hash); if (hash < ndx) ndx++; } else { ndx++; } } var swapPos = 0; for (var i = 0; i < len; i++, nEvals++) { var cur = array[offset + i]; if (cur != sentinel && i == (cur % len)) Swap(array, offset, i, swapPos++); } for (var i = swapPos; i < len; nEvals++) { var cur = array[offset + i]; if (cur == sentinel) return true; // got dups. else i++; } // Let's assume C# supports tail recursion ;-) // Then => look ma, O(1) extra storage space. return FindInPlace(array, offset + swapPos, ref nEvals); } private static void Swap(int[] array, int offset, int first, int second) { var tmp = array[offset + first]; array[offset + first] = array[offset + second]; array[offset + second] = tmp; } } 

Por lo tanto, si asumimos por un momento que c # admite la recursión de cola y no contamos los cuadros de stack usados ​​como espacio adicional, tiene O (1) requisitos de espacio.

El autor menciona que tiene una complejidad de tiempo O (N) -ish. Las pruebas (limitadas) (a diferencia de un análisis de complejidad computacional) que realicé indicaron que está más cerca de O (N log N).

 Array Size Dup Position #Evals 12 7 26 12 - 35 100,000 80,000 279,997 100,000 - 453,441 

Para el caso general, este problema no parece tener una solución debido a las fuertes restricciones de complejidad y la entrada desenfrenada.

Está claro, que necesita al menos N pasos para VER incluso todas las entradas. Entonces no puede ser más rápido que O(n) .

Ahora, para asegurarse de detectar todos los duplicados posibles, tiene diferentes posibilidades:

  • Compara cada número con cualquier otro número, esto no requiere mucho espacio adicional, pero toma O(n^2)
  • Haga la comparación de una manera más inteligente, intercambiando los enteros en el espacio disponible. Esto permite “almacenar información” en la secuencia misma. En realidad, comparar todos los números entre sí generalmente se hace en algoritmos de clasificación . Los algoritmos de clasificación conocidos más rápidos que no requieren espacio adicional necesitan tiempo O(n log n) . Wikipedia tiene un informe bastante extenso con muchas fonts . Por lo tanto, nunca puede obtener su requisito de tiempo de esa manera. ( algunos cuadros de comparación de algoritmos de clasificación conocidos )
  • Podría hacer una contabilidad con un hash-map que podría permitirle tomar solo el tiempo lineal O(n) , pero esa contabilidad debe almacenarse en algún lugar . De lo contrario, simplemente “olvidará” qué números ya ha visto. Desafortunadamente, la contabilidad requerirá más espacio si aumenta su entrada porque tiene tantos números diferentes para recordar. Por lo tanto, es imposible tener la misma cantidad fija de memoria y comparar secuencias de entrada arbitrariamente largas. Por lo tanto, tendrías que violar el espacio constante O(1) .

Como señala @Atishay en su respuesta, puede haber una solución si tiene una entrada muy restringida. Aquí se requiere que tenga una matriz de tamaño n los valores posibles estén solo en el rango [0,n-2] . Este requisito garantiza que DEBE haber un duplicado en alguna parte porque hay menos valores diferentes que los elementos en la matriz. Con ese conocimiento y el rango específico de valores, puede hacerlo. Pero esto utiliza suposiciones muy estrechas y no resuelve el problema general planteado en la pregunta.

Editar

Tal como se aclaró en los comentarios, existe un límite inferior comprobado para la complejidad temporal de los algoritmos de clasificación basados ​​en la comparación. Para referencia, mira aquí:

El filtro Bloom es un hashset eficiente en el espacio con una tasa de positivos falsos sintonizables. La posibilidad de falso positivo significa que tienes que volver atrás y verificar si hay un duplicado real cuando recibes un golpe del BF, introduciendo un término N ^ 2, pero el coeficiente es ~ exp (- (espacio adicional utilizado para el filtro)). Esto produce un espacio interesante de intercambio de espacio vs tiempo.

No tengo una prueba de que la pregunta planteada sea insoluble, pero en general “aquí hay un espacio de intercambio interesante” es una buena respuesta a un problema insoluble.

una implementación que usa un int único como una variable temporal … esto está usando vectores de bits /

  public static boolean isUniqueChars(String str) { int checker = 0; for (int i = 0; i < str.length(); ++i) { int val = str.charAt(i) - 'a'; if ((checker & (1 << val)) > 0) return false; checker |= (1 << val); } return true; } 

o mi implementación previa de O (n ^ 2) sin usar ninguna variable de temperatura

 public static bool isDuplicate(char[] str) { if (str == null) return false; int len = str.length; if (len < 2) return false; for (int i = 1; i < len; ++i) { for (int j = 0; j < len; ++j) { if (str[i] == str[j]) return true; } } return false; } 

Ejemplo de limpieza para determinar duplicados con O (n) por tiempo y O (1) por espacio:

 public class DuplicateDetermineAlgorithm { public static boolean isContainsDuplicate(int[] array) { if (array == null) { throw new IllegalArgumentException("Input array can not be null"); } if (array.length < 2) { return false; } for (int i = 0; i < array.length; i++) { int pointer = convertToPositive(array[i]) - 1; if (array[pointer] > 0) { array[pointer] = changeSign(array[pointer]); } else { return true; } } return false; } private static int convertToPositive(int value) { return value < 0 ? changeSign(value) : value; } private static int changeSign(int value) { return -1 * value; } } 
 public static void getDuplicatesElements (Integer arr[]){ //Status array to track the elements if they are already considered boolean status[] = new boolean [arr.length]; //Flag to mark the element found its duplicate boolean dupFlag = false; //Output string String output = ""; //Count of duplicate elements found int count = 0; //Initialize status array with all false ie no duplicates for (int i = 0; i < arr.length; i++) { status[i] = false; } //first loop to check every element for (int i = 0; i < arr.length - 1; i++) { //Initialize every element to no duplicate dupFlag = false; //Check if this element is not already found duplicate, if not, check now. if (!status[i]){ for (int j = i+1; j < arr.length; j++){ if (arr[i] == arr[j]){ dupFlag = true; status[j] = true; } } } if (dupFlag){ output = output + " " + arr[i]; count++; } } System.out.println("Duplicate elements: " + output ); System.out.println("Count: " + count ); } 

Renuncia

No tengo una respuesta pero mis pensamientos son demasiado extensos para un comentario. Además, quería escribirlos, por lo que las tres horas que paso pensando en una solución no se desperdician por completo. Espero darte un punto de vista diferente, pero si no te gusta perder tu tiempo, no sigas leyendo. O solo abajo, vote esta respuesta, vale la pena 🙂

Para reactivar nuestro pensamiento visual, tengamos una matriz de ejemplo: 50 100 150 -2 -1 0 1 2 3 4 . Como seguramente puede decir, no tiene duplicados, por lo que nuestro algoritmo debería dar como resultado FALSE . Además, su longitud es 10 .

Paso A: Cuente en el tiempo O (N)

Vamos a ignorar la restricción de memoria adicional por ahora (en realidad, violarla realmente mal, asumiendo que podemos tener O(\inf) memoria adicional 🙂 y guardar en una matriz infinita ficticia (también es doblemente infinita, ya que permite indeces negativos también) los conteos para cada número entero. Para nuestra entrada, esta matriz se vería así:

 ...000001111111000...00100...00100...001000000... ^ ^ ^ [index -2] [index 50] [index 150] 

Si alguno de los elementos de la matriz es mayor que 1 , entonces tenemos un duplicado y el algoritmo debería devolver TRUE .

Paso B: Mapa -inf..inf a 0..N en O (N) tiempo

Supongamos que tenemos un mapa f(x):-inf..inf -> 0..N que puede comprimir nuestra matriz infinita a una matriz de tamaño N, y además hacerlo en tiempo O (N). Esto es lo que hashing idealmente hace. Tenga en cuenta que no nos importa mantener el orden de la matriz, ya que solo nos importa si tiene elementos que están por encima de 1. Por lo tanto, podemos combinar estos dos pasos y eliminar la necesidad de memoria in fi nita, ¡yay! Todavía estamos usando una memoria O (N) adicional (de hecho, exactamente N conteos) para mantener los valores de conteo. El siguiente paso sería deshacerse de eso.

Paso C: usar el primer elemento como un interruptor

Antes de explicar este paso, observe que realmente no necesitamos almacenar ningún conteo mayor que 1. La primera vez que queremos boost un contador y notamos que ya tiene el valor de 1, ¡sabemos que encontramos un duplicado! Entonces, 1 bit de memoria por contador es suficiente. Esto reduce la memoria requerida a O (lg (N)), pero realmente no nos preocupamos por esto, ya que no es lo suficientemente bueno. La parte importante es que 1 bit de memoria por contador es suficiente.

Ahora vamos a explotar el hecho de que podemos modificar nuestra matriz de entrada. Revisamos el conjunto y xor todos los elementos con el valor del primer elemento. Si el resultado es menor que el valor antes de la operación, lo cambiamos a ese resultado. También almacenamos el primer elemento por separado como sw a un costo adicional de memoria O (1).

Ahora, podemos usar el primer elemento almacenado sw y la matriz transformada para codificar en los recuentos del paso de recuento (pasos A + B) de la siguiente manera: considerando el elemento con el índice k de A , si A[f(A[k])] < A[f(A[k])] xor sw entonces el recuento es zero que significa que el elemento que estamos considerando - A[k] - no se ha visto antes, entonces cambiamos A[f(A[k])] a A[f(A[k])] xor sw . Si, de lo contrario, A[f(A[k])] > A[f(A[k])] xor sw entonces el recuento es one que significa que el elemento que estamos considerando - A[k] - ya se ha visto antes , entonces es un duplicado

Asumiendo el mapa:

 f(-2 xr 50) -> 0 f(-1 xr 50) -> 1 f(0) -> 2 f(1) -> 3 f(2) -> 4 f(3) -> 5 f(4) -> 6 f(86) -> 7 f(150) -> 8 f(1337) -> 9 

y después de realizar los pasos en el siguiente orden: step c; step a+b step c; step a+b la matriz de entrada se ve así:

 50(0) 100(86) 150(164) -2(-2 xr 50) -1(-1 xr 50) 0(50) 1(51) 2(48) 3(49) 4(54) [intermediate state, not stored in memory] 0 86 150 -2 xr 50 -1 xr 50 0 1 2 3 4 [state after step c] 0 86 *164* -2 xr 50 -1 xr 50 0 1 2 3 4 [counted element 0] 0 86 164 -2 xr 50 -1 xr 50 0 1 *48* 3 4 [counted element 1] 0 86 164 -2 xr 50 -1 xr 50 0 1 48 *49* 4 [counted element 2] *50* 86 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 3] 50 *100* 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 4] 50 100 !164! -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 5] 

Al tratar de contar el elemento con el índice 5 que es 0 , vemos que ya había un 0 en la matriz. (porque A[f(A[5])] es 164 que es mayor que 164 xr 50 ) Por lo tanto, emitimos TRUE y el algoritmo finaliza.

Moraleja de la historia

Si no se nos permite suficiente memory x time , estamos obligados a olvidarnos de algo y cometer un error.

Lo siento

Desafortunadamente, no tenemos una función hash perfecta, y no podemos simplemente crear memoria de la nada, por lo que un enfoque tradicional no funcionaría bajo las restricciones requeridas. El algoritmo al que apunta la respuesta dada por OP puede ser modificado para que permita el uso de números que se interpretan como indecisiones de matriz quedaría fuera de los límites de la matriz, dada una función hash perfecta. Pero incluso entonces, tiene que ser inventado cómo usarlo para detectar la duplicación, en lugar de encontrar uno garantizado que exista ...

De todos modos, un problema interesante.

 import java.util.HashSet; import java.util.Set; public class FindDups { public static void main(String[] args) { int a[]={1,2,3,3,4}; Set s=new HashSet(); for(int i=0;i