Compara dos matrices de enteros con la misma longitud

Question

[Descripción] Dadas dos matrices de enteros con la misma longitud. Diseña un algoritmo que pueda juzgar si son iguales. La definición de "igual" es que, si estas dos matrices estuvieran ordenadas, los elementos en la posición correspondiente deberían ser iguales.

[Example] 
<1 2 3 4> = <3 1 2 4> 
<1 2 3 4> != <3 4 1 1> 

[Limitación] El algoritmo debe requerir espacio adicional constante, y O (n) tiempo de ejecución.

Answer 1

Usted puede tratar de un enfoque probabilístico - convertir las matrices en una serie de alguna enorme base B y mod por algún primo P, por ejemplo suma B^a_i para todos i mod algunos grandes-ish P. Si ambos salen al mismo número, intente de nuevo tantos primos como desee. Si es falso en cualquier intento, entonces no es correcto. Si pasan suficientes desafíos, entonces son iguales, con alta probabilidad.

Hay una prueba trivial de B>N, P> número más alto. Entonces debe haber un desafío que no se puede cumplir. En realidad, este es el enfoque determinista, aunque el análisis de complejidad podría ser más difícil, dependiendo de cómo la gente vea la complejidad en términos del tamaño de la entrada (en oposición a solo el número de elementos).

Answer 2

1. Insertar todos los elementos de la primera matriz en una tabla hash
2. intenta insertar todos los elementos de la segunda matriz en la misma tabla hash - para cada inserto de elemento ya debería estar allí

Ok, esto no es con un espacio extra constante, pero es lo mejor que puedo encontrar en este momento :-). ¿Hay otras restricciones impuestas a la pregunta, como por ejemplo al entero más grande que se puede incluir en la matriz?

Answer 3

(probablemente demasiado complejo para una pregunta de la entrevista.)

(Puede utilizar O (N) tiempo para comprobar el min, max, sum, SUMSQ, etc. son iguales primero.)

Uso no-extra-space radix sort para ordenar las dos matrices en el lugar. O (N) complejidad del tiempo, O (1) espacio.

Luego compárelos usando el algoritmo habitual. O (N) complejidad del tiempo, O (1) espacio.

(Proporcionada (max − min) de las matrices es de O (N ^k) con una k finito.)

Answer 4

Para cada matriz, utilizar el conteo técnica tipo para construir el recuento del número de elementos menos igual o igual a un elemento en particular. Luego compare las dos matrices auxiliares construidas en cada índice, si son iguales a las matrices r igual, de lo contrario, no lo son. La clasificación de recuento requiere O (n) y la comparación de matriz en cada índice es nuevamente O (n), por lo tanto, es totalmente O (n) y el espacio requerido es igual al tamaño de dos matrices. Aquí hay un enlace para contar el tipo http://en.wikipedia.org/wiki/Counting_sort.

Answer 5

Algunas respuestas son básicamente correctas, aunque no lo parezcan. El enfoque de tabla hash (para un ejemplo) tiene un límite superior basado en el rango tipo involucrado en lugar del número de elementos en las matrices. Al menos por la mayoría de las definiciones, eso hace que el (límite superior en) el espacio sea constante, aunque la constante puede ser bastante grande.

En teoría, podría cambiar eso de un límite superior a una cantidad constante de espacio. Sólo por ejemplo, si estuviera trabajando en C o C++, y era una matriz de char, podría utilizar algo como:

size_t counts[UCHAR_MAX]; 

Desde UCHAR_MAX es una constante, la cantidad de espacio utilizado por la matriz es también una constante.

Editar: Me gustaría tener en cuenta que un límite en los rangos/tamaños de los elementos implicados está implícito en casi todas las descripciones de complejidad algorítmica. Solo por ejemplo, todos "sabemos" que Quicksort es un algoritmo O (N log N). Sin embargo, eso solo es cierto si suponemos que comparar e intercambiar los elementos que se ordenan requiere tiempo constante, lo que solo puede ser cierto si vinculamos el rango. Si el rango de elementos implicados es lo suficientemente grande como para que no podamos tratar una comparación o un intercambio como tomar un tiempo constante, entonces su complejidad sería algo así como O (N log N log R), donde R es el rango, por lo que log R se aproxima la cantidad de bits necesarios para representar un artículo.

Answer 6

¿Es esta una pregunta capciosa? Si los autores asumieron que los enteros se encuentran dentro de un rango determinado (2^32, etc.), entonces el "espacio extra constante" podría ser simplemente una matriz de tamaño 2^32 en la que se cuentan las ocurrencias en ambas listas.

Si los enteros son unranged, no se puede hacer.

Answer 7

Puede agregar cada elemento en un hashmap < entero, entero>, con las siguientes reglas: la matriz A es la sumadora, la matriz B es la removedora. Al insertar desde la matriz A, si la clave no existe, insértela con un valor de 1. Si la clave existe, incremente el valor (mantenga una cuenta). Al eliminar, si la clave existe y es mayor que 1, reduzca en 1. Si la clave existe y es 1, elimine el elemento.

Ejecutar a través del conjunto A seguido del conjunto B utilizando las reglas anteriores. Si en algún momento durante la fase de eliminación, el conjunto B no encuentra un elemento, puede devolverlo de inmediato. Si después de que tanto el sumador como el eliminador hayan finalizado, el hashmap está vacío, las matrices son equivalentes.

Editar: El tamaño de la tabla hash será igual al número de valores distintos en la matriz ¿se ajusta esto a la definición de espacio constante?

Answer 8

int dado están en el rango -n .. + na manera simple para comprobar la equidad puede ser el siguiente (pseudo código):

// a & b are the array 
accumulator = 0 
arraysize = size(a) 
for(i=0 ; i < arraysize; ++i) { 
    accumulator = accumulator + a[i] - b[i] 
    if abs(accumulator) > ((arraysize - i) * n) { return FALSE } 
} 
return (accumulator == 0) 

acumulador debe ser capaz de almacenar número entero con rango = + - arraysize * n

Answer 9

Imagino que la solución requerirá algún tipo de transformación que sea tanto asociativa como conmutativa y garantiza un resultado único para un conjunto único de entradas. Sin embargo, no estoy seguro de si eso existe.

Answer 10

Yo afirmo que: A menos que se especifique el rango de entrada, entonces es IMPOSIBLE resolver en un espacio adicional, y O (n) tiempo de ejecución.

Me alegrará que se demuestre que estoy equivocado, por lo que puedo aprender algo nuevo.

Answer 11

¿Qué tal esto? XOR todos los números en ambas matrices. Si el resultado es 0, tienes una coincidencia.

Answer 12

public static boolean match(int[] array1, int[] array2) { 

     int x, y = 0; 

     for(x = 0; x < array1.length; x++) { 
       y = x; 
       while(array1[x] != array2[y]) { 
         if (y + 1 == array1.length) 
           return false; 
         y++; 
       } 
       int swap = array2[x]; 
       array2[x] = array2[y]; 
       array2[y] = swap; 
     } 

     return true; 
}