arrays - resueltos - que es un array en java

encuentre si dos arreglos contienen el mismo conjunto de enteros sin espacio adicional y más rápido que NlogN

Question

Me encontré con este post , que reporta la siguiente pregunta de entrevista:

Dados dos matrices de números, ¿encontrar si cada una de las dos matrices tiene el mismo conjunto de números enteros? ¿Sugerir un algo que pueda ejecutarse más rápido que NlogN sin espacio adicional?

Lo mejor que se me ocurre es lo siguiente:

1. (a) ordena cada matriz, y luego (b) tiene dos punteros que se mueven a lo largo de las dos matrices y comprueba si encuentras valores diferentes ... pero el paso (a) ya tiene complejidad NlogN :(

2. (a) escanee la matriz más corta y coloque valores en un mapa, y luego (b) escanee la segunda matriz y verifique si encuentra un valor que no esté en el mapa ... aquí tenemos una complejidad lineal, pero utilizamos espacio adicional

... entonces, no puedo pensar en una solución para esta pregunta.

Ideas?

Gracias por todas las respuestas. Siento que muchos de ellos tienen razón, pero decidí elegir el de Ruslik , porque me da una opción interesante en la que no pensé.

Answer 1

¿Por qué no encuentro la suma, producto, xor de todos los elementos de una matriz y los comparo con el valor correspondiente de los elementos de la otra matriz?

el xor de elementos de ambas matrices puede dar cero si es como

2,2,3,3 1,1,2,2

pero ¿qué pasa si comparas el xor de los elementos de dos matrices para que sean iguales?

considera esto

10,3 12,5

Aquí xor de ambas matrices será igual !!! (10 ^ 3) = (12 ^ 5) = 9 pero su suma y producto son diferentes. ¡Creo que dos conjuntos de elementos diferentes no pueden tener la misma suma, producto y xor! Esto se puede analizar mediante un simple examen de valores de bits. ¿Hay algo malo en este enfoque?

Answer 2

Aquí hay un algoritmo co-rp:

En tiempo lineal, itere sobre la primera matriz (A), construyendo el polinomio Pa = A [0] - x) (A [1] -x) ... (A [n-1] - x). Haga lo mismo para la matriz B, nombrando este polinomio Pb.

Ahora queremos responder la pregunta "is Pa = Pb?" Podemos comprobarlo probabilísticamente de la siguiente manera. Seleccione un número r uniformemente aleatorio del rango [0 ... 4n] y calcule d = Pa (r) - Pb (r) en tiempo lineal. Si d = 0, devuelve verdadero; de lo contrario devuelve falso.

¿Por qué es esto válido? En primer lugar, observe que si las dos matrices contienen los mismos elementos, entonces Pa = Pb, entonces Pa (r) = Pb (r) para todo r. Teniendo esto en cuenta, podemos ver fácilmente que este algoritmo nunca rechazará erróneamente dos matrices idénticas.

Ahora debemos considerar el caso en el que las matrices no son idénticas. Por el Lema de Schwart-Zippel, P (Pa (r) - Pb (r) = 0 | Pa! = Pb) <(n / 4n). Entonces, la probabilidad de que aceptemos las dos matrices como equivalentes cuando no lo son es <(1/4).

Answer 3

Asumiré que los enteros en cuestión son de tamaño fijo (por ejemplo, 32 bits).

Luego, la ordenación rápida de radios de ambas matrices en su lugar (también conocido como "quicksort binario") es un espacio constante y O (n).

En el caso de los enteros sin límites, creo (pero no puedo probar, incluso si es probable que sea factible) que no puede romper la barrera O (nk), donde k es el número de dígitos del mayor entero en cualquier matriz.

Si esto es mejor que O (n log n) depende de cómo se supone que k escala con n, y por lo tanto depende de lo que el entrevistador espera de usted.

Answer 4

Dijo "sin espacio adicional" en la pregunta, pero supongo que en realidad quiere decir "con O (1) espacio adicional".

Supongamos que todos los enteros en las matrices son menores que k . Luego, puede usar la clasificación de radix en el lugar para ordenar cada matriz en el tiempo O ( n log k ) con O (log k ) espacio adicional (para la pila, como lo indica yi_H en los comentarios), y comparar las matrices ordenadas en el tiempo O ( n log k ). Si k no varía con n , entonces has terminado.

Answer 5

El supuesto habitual para este tipo de problemas es Theta (log n) -bit palabras, porque ese es el mínimo necesario para indexar la entrada.

1. La respuesta de evaluación polinómica de sshannin funciona bien en campos finitos, lo que evita las dificultades con los registros de precisión limitada. Todo lo que necesitamos es un primo de lo apropiado (fácil de encontrar bajo los mismos supuestos que apoyan una gran cantidad de criptografía de clave pública) o un polinomio irreducible en (Z / 2) [x] del grado apropiado (la dificultad aquí es multiplicar los polinomios rápidamente, pero creo que el algoritmo sería o (n log n)).

2. Si podemos modificar la entrada con la restricción de que debe mantener el mismo conjunto, entonces no es demasiado difícil encontrar espacio para la clasificación de radix. Seleccione el elemento (n / log n) de cada matriz y particione ambas matrices. Ordena las piezas de tamaño (n / log n) y compáralas. Ahora use la ordenación de radix en las piezas de tamaño (n - n / log n). De los elementos procesados ​​anteriormente, podemos obtener n / log n bits, donde el bit i está activado si a [2 * i]> a [2 * i + 1] y está desactivado si a [2 * i] <a [2 * i + 1]. Esto es suficiente para admitir una ordenación de radix con n / (log n) ^ 2 depósitos.

Answer 6

En el modelo de árbol de decisión algebraico, existen límites inferiores conocidos de Omega (NlogN) para calcular la intersección de conjuntos (independientemente de los límites de espacio).

Por ejemplo, consulte aquí: http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/06-algebraic-tree.pdf

Por lo tanto, a menos que realice manipulaciones de bits inteligentes / enfoques de tipo hash, no podrá hacerlo mejor que NlogN.

Por ejemplo, si solo usaste comparaciones, no puedes hacerlo mejor que NlogN.

Answer 7

Estaba pensando si había una manera en la que pudiera agrupar y acumular las dos matrices y compararlas, asumiendo que la función de hashing no produce colisiones entre dos patrones diferentes.

Answer 8

No estoy seguro de que haya entendido correctamente el problema, pero si está interesado en los enteros que están en ambas matrices:

Si N >>>>> 2 ^ SizeOf (int) (cuenta de bit para entero (16, 32, 64)) hay una solución:

a = Array(N); //length(a) = N;
b = Array(M); //length(b) = M; 
//x86-64. Integer consist of 64 bits.

for i := 0 to 2^64 / 64 - 1 do  //very big, but CONST
  for k := 0 to M - 1 do
    if a[i] = b[l] then doSomething;   //detected

for i := 2^64 / 64 to N - 1 do
 if not isSetBit(a[i div 64], i mod 64) then
   setBit(a[i div 64], i mod 64);

for i := 0 to M - 1 do
 if isSetBit(a[b[i] div 64], b[i] mod 64) then doSomething; //detected

O (N), sin estructuras adicionales.

Answer 9

Para cada número entero i compruebe que el número de apariciones de i en los dos arreglos sea cero o ambos distintos de cero, iterando sobre los arreglos.

Como el número de enteros es constante, el tiempo de ejecución total es O(n) .

No, no haría esto en la práctica.

Answer 10

Puede probar un enfoque probabilístico eligiendo una función conmutativa para la acumulación (p. Ej., Adición o XOR) y una función hash parametrizada.

unsigned addition(unsigned a, unsigned b);
unsigned hash(int n, int h_type);

unsigned hash_set(int* a, int num, int h_type){
    unsigned rez = 0;
    for (int i = 0; i < num; i++)
        rez = addition(rez, hash(a[i], h_type));
    return rez;
};

De esta manera, el número de intentos antes de que usted decida que la probabilidad de falsos positivos estará por debajo de cierto umbral no dependerá del número de elementos, por lo que será lineal.

EDITAR : En el caso general, la probabilidad de que los conjuntos sean los mismos es muy pequeña, por lo que esta comprobación O (n) con varias funciones hash puede usarse para el prefiltrado: para decidir lo más rápido posible si son seguramente diferentes o si existe una probabilidad de ellos son equivalentes, y si se debe usar un método determinista lento. La complejidad promedio final será O (n), pero en el peor de los casos tendrá la complejidad del método determinista.

Answer 11

Puede romper la barrera O (n * log (n)) si tiene algunas restricciones en el rango de números. Pero no es posible hacer esto si no puede usar ninguna memoria adicional (necesita restricciones realmente tontas para poder hacerlo).

También me gustaría señalar que incluso O (n log (n)) con clasificación no es trivial si tiene O (1) límite de espacio, ya que la ordenación de combinación usa O (n) espacio y quicksort (que ni siquiera es estricto o (n log (n)) necesita O (log (n)) espacio para la pila. Debe usar heapsort o smoothsort.

A algunas compañías les gusta hacer preguntas que no se pueden resolver y creo que es una buena práctica. Como programador, debe saber qué es posible y cómo codificarlo y también cuáles son los límites para que no pierda el tiempo. algo que no es factible.

Marque esta pregunta para conocer un par de buenas técnicas: Algoritmo para determinar si dos matrices tienen miembros idénticos

Answer 12

Si las matrices tienen el mismo tamaño, y se garantiza que no habrá duplicados, sume cada una de las matrices. Si la suma de los valores es diferente, entonces contienen diferentes enteros.

Editar: A continuación, puede sumar el registro de las entradas en los arrays. Si eso también es lo mismo, entonces tienes las mismas entradas en la matriz.

Answer 13

Todo lo que sé es que la clasificación basada en comparación no puede ser más rápida que O (NlogN), por lo que podemos eliminar la mayoría de "común" tipos basados ​​en la comparación. Estaba pensando en hacer una especie de cubo. Quizás si esta pregunta se preguntara en una entrevista, la mejor respuesta sería primero aclarar qué tipo de datos representan esos enteros. Por ejemplo, si representan la edad de una persona, entonces sabemos que el rango de valores de int es limitado, y podemos usar la clasificación de cubo en O (n). Sin embargo, esto no estará en su lugar ...

Answer 14

Un caso especial, no más difícil es cuando una matriz contiene 1,2, .., n. Esto fue discutido muchas veces:

• ¿Cómo saber si una matriz es una permutación en O (n)?
• Algoritmo para determinar si la matriz contiene n ... n + m?
• mathoverflow

y, a pesar de muchos intentos, no se mostraron soluciones deterministas utilizando O (1) espacio y O (n) tiempo. O puede engañar a los requisitos de alguna manera (reutilizar el espacio de entrada, suponiendo que los enteros están delimitados) o usar una prueba probabilística.

Probablemente este es un problema abierto.