O (n) Algoritmo para encontrar si 2 matrices tienen 2 elementos que se suman a un número

Question

Estoy estudiando para un examen y encontré esta pregunta que parece un poco complicada.

Deje A [1 ... n] y B [1 ... n] ser 2 matrices de números enteros de modo que cada elemento de A o B esté en el rango de 0 a m donde m = O (n). (estoy asumiendo que significa m < n?)

Necesitamos diseñar un O algoritmo (n) que encuentra dos elementos A [i] y B [j] de tal manera que A [i] + B [j ] = un número dado k. Si no existen, lanzamos un mensaje de error.

Ahora clasificarlos estaría fuera de la cuestión, ya que los mejores algoritmos de clasificación son O (n lg n).

Quizás use una tabla hash ... O simplemente cree una matriz más pequeña X de longitud m, de modo que cada índice cuente las ocurrencias de un número en A ... luego pasamos por B .. calcular diff = k - B [j ] .. y comprobar X [diff] .. si es mayor que cero, entonces sí, existe, entonces podríamos pasar por un nuevo para encontrar su índice ..

¿Qué piensan ustedes

Answer 1

m = O(n) significa m está limitado por un múltiplo constante de n, no necesariamente más pequeño que él.

Lo que puedes hacer es esto. Obtenga una matriz con el tamaño k+1 (por lo que la memoria O(m) que también es O(n)). Llame a esta matriz C. Inicialice todos los valores como no marcados, digamos -1. Esto es O(m) que también es O(n).

Ahora sabes que k <= 2m porque A[i] y B[i] son ambos <= m.Por lo tanto, vaya a través de la matriz A, marque en C todos k-A[i], entonces C[k-A[i]] = i (Esto es si k-A[i] >= 0suponiendo que los índices comiencen desde 0). Esto es O(n). A continuación, vaya a través de la matriz B y para cada B[j] marque si C[B[j]] ya ha sido marcado. Si es así, entonces C[B[j]] marca un cierto índice en A donde B[j]+A[C[B[j]]] = k. Pasando por B y marcando la marca también es O(n). Si no encuentras una coincidencia, no hay tal pareja.

El algoritmo general es O(n).

Aquí se muestra un ejemplo:

n = 5 
m = 15 
A = [1 7 4 2 10] 
B = [8 14 3 13 11] 
k = 20 

Después de pasar A, se obtiene:

C: [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 1 -1 -1 2 -1 3 0 -1] 

(espaciamiento es para una mejor visualización) A continuación, se comprueba contra B:

B[0] -> C[8] -> -1 mismatch 
B[1] -> C[14] -> -1 mismatch 
B[2] -> C[3] -> -1 mismatch 
B[3] -> C[13] -> 1 match -> B[3] + A[1] = 20 

B[3] era 13 y A[1] era 7.

Answer 2

Usaremos una tabla hash que contiene la diferencia entre cada elemento en la primera matriz y la suma. Básicamente solo itere a través de la primera matriz, calcule la diferencia entre la suma y cada elemento de la matriz y guárdela en la tabla hash. Luego itere a través de la segunda matriz, verificando si cada número aparece en la tabla hash

Answer 3

Puede ordenar en O (n) usando el método de la tabla hash que describió (solo podría almacenar un booleano en vez de un int, ya que solo necesito saber si existe). En general, los géneros de comparación no son mejores que O (n lg n), pero si conoce ciertas restricciones, puede hacerlo mejor (o si puede usar géneros no comparativos como radix sort (que creo que puede usar aquí también)) . Básicamente:

1. Inicialice una matriz, A ', de tamaño n y establezca todos los valores en falso.
2. Para cada elemento en A, establezca el índice correspondiente en A 'en verdadero.
3. Para cada elemento en A ', si el valor es verdadero, añada el índice a otra matriz A' '.
4. A '' ahora es una A, con duplicados eliminados.
5. Repetir para B.

El problema debe ser bastante trivial ahora que tiene A y B ordenadas.