¿Cómo encuentra el número de pares en una matriz de enteros que suman al menos k? ¿Es posible hacer esto en tiempo lineal?

O (nlogn) como se menciona en otras respuestas. pero,

Sí, es posible en tiempo lineal O (n), si n es [matemática]> -1 [/ matemática]. pero la complejidad del espacio también es O (n). Compromiso 😛

Usando MAP (mapeando números en el índice y almacenando su frecuencia) .

Tome una matriz A [n] y haga el mapeo en orden ascendente. En)

Si no se da el número, entonces A [i] = 0, de lo contrario, tiene el valor de la frecuencia de ese número.

Luego toma otra matriz y almacena su suma de prefijo en un índice particular.

A continuación se muestra el algoritmo.

1. Cree un mapa hash para almacenar la frecuencia de cada número en la matriz. La complejidad del tiempo es O (n).
2. Crea una matriz de suma de prefijos de su frecuencia y la almacena. En)
3. En el siguiente recorrido, para cada elemento, verifique si se puede combinar con cualquier otro elemento (comenzando desde i + 1) para obtener la suma deseada. Incremente el contador en consecuencia. (a [i] – k = a [j])
4. Después de encontrar el límite mínimo, tome la diferencia de la suma del prefijo del último elemento y el elemento más a la izquierda del elemento límite (si el elemento límite es el primer elemento de la matriz, tómelo como 0)
5. Después de completar el segundo recorrido, tendríamos el doble del valor requerido almacenado en el mostrador porque cada par se cuenta dos veces. Por lo tanto, divida el conteo entre 2 y regrese.

Ej:

X = [1,2,2,3,4,3,6]

Mapa M = [(1,1), (2,2), (3,2), (4,1), (6,1)] [Número y su frecuencia]

A = [0,1,2,2,1,0,1,0,…, 0]

Prefijo suma de fre. = [1,3,5,6,7]

si suma es al menos k = 3, entonces

para i = 1, el punto límite es 2, 1 + 2> = 3, Tome la diferencia de frecuencia [7–1] = 6 pares.

para i = 2, el punto límite es 1,2 + 1> = 3, tome la diferencia de frecuencia [7 – o] = 7 pares.

para i = 3, el punto límite es 1,3 + 1> = 3, Tome la diferencia de frecuencia [7 – o] = 7 pares.

para i = 4, el punto límite es 1,4 + 1> = 3, tome la diferencia de frecuencia [7 – o] = 7 pares.

para i = 6, el punto límite es 1,6 + 1> = 3, Tome la diferencia de frecuencia [7 – o] = 7 pares.

Par total = [matemáticas] (6 + 7 + 7 + 7 + 7) = 34/2 = 17 [/ matemáticas].

¡Dividir por 2 porque contamos cada par 2 veces! (Ej. (1,2) = (2,1))

Feliz codificación !!

El problema se puede resolver en [math] O (n \ log {n}) [/ math] time.

Ordenemos la matriz y luego revisemos sus números: para el elemento [math] i [/ math] -th [math] x [/ math] en la matriz, encontraremos la primera posición [math] pos [/ math] de el elemento mínimo mayor o igual a [math] k – x [/ math]. Podemos hacer esto usando la búsqueda binaria. Para evitar contar algunos pares dos veces, buscaremos dicha posición solo en la parte [math] [i + 1, n) [/ math]. Una vez que encontramos tal posición [math] pos> i [/ math], significa que tenemos números [math] n – pos [/ math] no menores que [math] k – x [/ math] en [math] [i + 1, n) [/ math] parte, todo lo cual debe tenerse en cuenta.

Por ejemplo, si los números [matemáticos] = [5, 1, 2, 9, 3], k = 5 [/ matemáticos], luego de ordenar la matriz tenemos los números [matemáticos] = [1, 2, 3, 5, 9 ][/matemáticas]. Para el primer elemento [matemática] x = 1 [/ matemática] tenemos [matemática] kx = 5 – 1 = 4 [/ matemática]. El primer elemento [math] \ geq 4 [/ math] es 5, esto se puede encontrar mediante búsqueda binaria. Entonces tenemos 2 elementos que no son menores que 4. Para el próximo número 2, tenemos 3 elementos que no son menores que 3. Para el número 3, tenemos 4 elementos que no son menores que 2, pero debemos buscar solo en la parte restante, entonces sumamos 2 a la respuesta. Para el próximo número 5, tenemos 1 número por encima de 0 en la parte restante. En total, la respuesta es 2 + 3 + 2 + 1 = 8.

Los detalles de implementación (Python 3) están a continuación:

  def get_number_of_magic_pairs (números, k):
     sorted_numbers = sorted (números)
     número_de_pares = 0
     para i, número en enumerate (sorted_numbers):
         resto = k - número
         izquierda = i
         derecha = len (números)
         mientras derecha - izquierda> 1:
             mid = (izquierda + derecha) // 2
             if sorted_numbers [mid]> = resto:
                 derecha = medio
             más:
                 izquierda = medio
         número_de_pares + = len (números) - derecha
     devolver número_de_pares

La ordenación se puede hacer en [math] O (n \ log {n}) [/ math] time y para cada uno de los elementos [math] n [/ math] de la matriz hacemos una búsqueda binaria en [math] O (\ log {n}) [/ math] tiempo, por lo que, en general, la complejidad del algoritmo es [math] O (n \ log {n}) [/ math]. Esto es lo mejor que podemos hacer para una matriz sin clasificar. Para una matriz ordenada, podemos utilizar el método de dos punteros (descrito en otra respuesta) para lograr un tiempo lineal.