arrays - que - Compara dos matrices de enteros con la misma longitud

vectores en java netbeans

Question

[Descripción] Dadas dos matrices de enteros con la misma longitud. Diseñe 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 los mismos.

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

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

Answer 1

1. Insertar todos los elementos de la primera matriz en una tabla hash
2. Intente insertar todos los elementos de la segunda matriz en la misma tabla hash: para cada inserción en el elemento ya debería estar allí

Ok, esto no es con espacio extra constante, pero lo mejor que pude encontrar en este momento :-). ¿Existen otras restricciones impuestas a la pregunta, como por ejemplo el mayor entero que puede incluirse en la matriz?

Answer 2

¿Es esta una pregunta con trampa? Si los autores asumieron que los enteros están dentro de un rango dado (2 ^ 32, etc.), entonces "espacio constante adicional" podría ser simplemente una matriz de tamaño 2 ^ 32 en la que se cuentan las ocurrencias en ambas listas.

Si los enteros no están ordenados, no se puede hacer.

Answer 3

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

Answer 4

(Probablemente demasiado complejo para una pregunta de entrevista.)

(Puede usar el tiempo O (N) para verificar que el mínimo, máximo, suma, suma, etc. sean iguales primero).

Utilice la ordenación de radixes sin espacio adicional para ordenar las dos matrices en el lugar. O (N) complejidad de tiempo, O (1) espacio.

Luego compáralos usando el algoritmo usual. O (N) complejidad de tiempo, O (1) espacio.

(Siempre (máximo - mínimo) de las matrices es de O (N ^k ) con un k finito).

Answer 5

Afirmo que: a menos que se especifique el rango de entrada, es IMPOSIBLE resolverlo en un espacio adicional inmediato, y el tiempo de ejecución de O (n).

Estaré feliz de estar equivocado, de modo que pueda aprender algo nuevo.

Answer 6

Algunas respuestas son básicamente correctas, aunque no lo parezcan. El método de la tabla hash (por ejemplo, tiene un límite superior basado en el rango del tipo involucrado en lugar del número de elementos en los arreglos). Al menos según la mayoría de las definiciones, eso hace que el (límite superior) del espacio sea una 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 verdadera. Solo por ejemplo, si estuvieras trabajando en C o C ++, y fuera una matriz de caracteres, podrías usar algo como:

size_t counts[UCHAR_MAX];

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

Edición: anotaría para el registro que un límite en los rangos / tamaños de los elementos involucrados está implícito en casi todas las descripciones de la complejidad algorítmica. Solo por ejemplo, todos sabemos que Quicksort es un algoritmo O (N log N). Sin embargo, eso solo es cierto si asumimos que la comparación y el intercambio de los elementos que se clasifican toman un tiempo constante, lo que solo puede ser cierto si limitamos el rango. Si el rango de los elementos involucrados es lo suficientemente grande como para que ya no podamos tratar una comparación o un intercambio como un tiempo constante, entonces su complejidad se volvería algo así como O (N log N log R), donde R es el rango, entonces log R aproxima el número de bits necesarios para representar un elemento.

Answer 7

Me imagino que la solución requerirá algún tipo de transformación que sea asociativa y conmutativa y garantice un resultado único para un conjunto único de entradas. Sin embargo no estoy seguro si eso existe.

Answer 8

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

Answer 9

Podría agregar cada elemento en un hashmap <Integer, Integer>, con las siguientes reglas: la matriz A es el sumador, la matriz B es el removedor. 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 un recuento). Al eliminar, si la clave existe y es mayor que 1, redúzcala en 1. Si la clave existe y es 1, elimine el elemento.

Ejecutar a través de la matriz A seguido de la matriz B utilizando las reglas anteriores. Si en algún momento durante la fase de eliminación, la matriz B no encuentra un elemento, puede devolver inmediatamente falso. Si después de que tanto el sumador como el removedor hayan finalizado, el hashmap está vacío, los arreglos son equivalentes.

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

Answer 10

Puede probar un enfoque probabilístico: convierta los arreglos en un número en alguna base B y mod mediante algunos P primarios, por ejemplo, sume B^a_i para todos los mods y P grandes. Si ambos salen al mismo número, intente nuevamente para tantos números primos como desee. Si es falso en cualquier intento, entonces no son correctos. Si pasan suficientes desafíos, entonces son iguales, con alta probabilidad .

Hay una prueba trivial para B > N , P > mayor número. Por lo tanto, debe haber un desafío que no se puede cumplir. Este es realmente el enfoque determinista, aunque el análisis de complejidad puede ser más difícil, dependiendo de cómo las personas vean la complejidad en términos del tamaño de la entrada (en oposición al número de elementos).

Answer 11

dados int están en el rango -n .. + na una forma sencilla de verificar la equidad puede ser la 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)

el acumulador debe poder almacenar números enteros con rango = + - tamaño de matriz * n

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;
}