Dada una matriz ordenada, ¿cómo encontrarías dos números cuya suma es igual a un número dado en O (n)?

Podemos usar Hashing para resolver fácilmente este problema en tiempo lineal. La idea es insertar cada elemento de la matriz arr [i] en un mapa. También verificamos si la diferencia (arr [i], sum-arr [i]) ya existe en el mapa o no. Si la diferencia se ve antes, imprimimos el par y regresamos.

Consulte el último enfoque discutido aquí para la implementación.

Primero expongamos el problema. Se nos da una matriz [math] A [1] \ leq \ ldots \ leq A [n] [/ math] y un número x y necesitamos verificar la existencia de un par de índices [math] i [/ math] y [matemática] j [/ matemática] tal que [matemática] 1 \ leq i

El artículo explica la solución [matemática] O (n) [/ matemática] que funciona utilizando hashing. No supone que la matriz de entrada esté ordenada. Utiliza un espacio adicional [matemático] O (n) [/ matemático] y tiene un tiempo lineal, ya que se supone que la búsqueda y la adición en conjuntos hash toman tiempo constante.

Consideremos otra solución que también requiere tiempo lineal pero no utiliza ningún espacio adicional. Si [math] n = 2 [/ math] entonces nuestro problema es trivial y es suficiente para verificar si [math] A [1] + A [2] = x [/ math] o no. Este será nuestro caso base.

Suponga que [matemática] n> 2, [/ matemática] luego compare [matemática] A [1] + A [n] [/ matemática] con [matemática] x [/ matemática]. Si [matemática] A [1] + A [n] = x [/ matemática], entonces tenemos una solución donde [matemática] i = 1 [/ matemática] y [matemática] j = n [/ matemática].

Notamos que si [matemática] A [1] + A [n]> x [/ matemática] entonces [matemática] A [n] [/ matemática] no puede ser parte de ninguna solución y [matemática] j \ neq n [/ math] como para todos [math] 1 \ leq i \ leq n, A [i] + A [n]> x. [/ math] Para que podamos eliminar [math] A [n] [/ math] de Considerar y considerar un problema menor de tamaño [matemática] n – 1 [/ matemática] descrita como [matemática] A [1] \ leq \ ldots \ leq A [n-1] [/ matemática] y [matemática] x [/ matemáticas].

Por otro lado, si [matemática] A [1] + A [n]

Esto se conoce comúnmente en la programación competitiva como el enfoque de dos punteros.

Otro enfoque que puede funcionar y no necesita espacio auxiliar es la búsqueda binaria, pero su peor complejidad temporal es [matemática] O (n \ log n) [/ matemática]. Sin embargo, debe tener cuidado si se permiten duplicados ya que la implementación descuidada de la búsqueda binaria podría no distinguir el caso donde [matemática] A [i] + A [i] = x [/ matemática] es la única solución. Por ejemplo, [matemática] A = [2, 3, 5] [/ matemática] y [matemática] x = 6, [/ matemática] una solución incorrecta en ese caso consideraría que un par de elementos de [matemática] A [ / math] cuya suma es [math] x [/ math] existe.

La solución de Quora User funciona de manera más efectiva. Acabo de poner mi implementación en Ruby aquí:

def target_pair (arr, objetivo)
temp = {}
resultado = {}
arr.each do | x |
temp [x]? resultado [x] = objetivo – x: temp [objetivo – x] = verdadero
fin
resultado
fin

objetivo = 23
arr = 50.times.map {| x | rand (50)}

pone “# {arr.inspect} \ n \ n”
pone target_pair (arr, target) .to_s.gsub (‘=>’, ‘+’)

Imprimirá algo similar a esto:

[45, 43, 18, 25, 15, 46, 11, 7, 5, 3, 4, 23, 29, 37, 49, 0, 20, 34, 11, 13, 8, 4, 25, 17, 10 , 25, 32, 31, 30, 38, 38, 9, 14, 9, 11, 22, 42, 18, 45, 39, 16, 27, 23, 16, 46, 7, 26, 43, 33, 5 ]

{5 + 18, 0 + 23, 20 + 3, 8 + 15, 10 + 13, 14 + 9, 16 + 7}

Esta implementación de búsqueda binaria lo haría. ctci / main.go en master · amay0048 / ctci · GitHub

Eche un vistazo aquí para ver la declaración del problema que acompaña a la solución anterior.

La esencia:

1. Eliminar el primer elemento de la matriz
2. Objetivo = la diferencia entre el primer elemento y la suma que busca
3. Binario busca el resto de la matriz para el objetivo
4. Repita 1–3 hasta que encuentre la suma que está buscando o se quede sin elementos de la matriz

Actualizar

Según la descripción de Hassan AbouEisha, esto es realmente O n log n

También encontré este gran chat en mis viajes, espero que ayude a alguien Hoja de trucos de la complejidad del algoritmo Big-O

En realidad, la matriz no necesita ser ordenada. Todavía puede hacer este trabajo en O (n) complejidad de tiempo con cualquier matriz. Aquí hay un fragmento de JS. Genera una matriz de 50 enteros positivos aleatorios entre 1–50 y luego intenta encontrar los pares cuya suma es igual al objetivo (23 en este caso) en una sola pasada. Pruébelo en las herramientas de desarrollo de su navegador.

función getTargetPair (a, t) {
var ht = {}, // hash temporal
hr = {}; // resultado hash
a.forEach (e => ht [e]? hr [e] = te
: ht [te] = verdadero);
volver h;
}

var tgt = 23, // suma objetivo
arr = Array (30) .fill (). map (_ => ~~ (Math.random () * 50 + 1)),
res = {}; // resultado del acebo
res = getTargetPair (arr, tgt);
console.log (arr);
console.log (res);

paso 1- almacena todos los elementos de la matriz en hashset en o (n)

paso 2- para cada elemento i en la matriz verifique si (xi) está en el hashset, terminando este ciclo en o (n). siga imprimiendo los pares donde el cheque devuelve verdadero.

Recuerdo una maqueta de una entrevista de Google con esta misma pregunta:

Cómo: trabajar en Google: codificación de ejemplo / entrevista de ingeniería