Dado un conjunto entero ordenado y un número z, cuente todos los pares (x, y) en el conjunto de modo que x + y <z. ¿Se puede hacer en O (n)?

Si.
Para simplificar el problema, suponga que solo estamos interesados ​​en pares [matemática] (x, y) [/ matemática] de modo que [matemática] x

Bueno, si arreglamos algunos [matemática] x [/ matemática] (llamémosla [matemática] izquierda [/ matemática]), entonces podemos atravesar la matriz de derecha a izquierda y encontrar el índice más grande [matemática] derecha [/ matemática] para la cual [matemática] a [izquierda] + a [derecha]

Pero [math] left [/ math] era simplemente cualquier índice fijo. Por lo tanto, podemos simplemente fijar [matemáticas] a la izquierda [/ matemáticas] como índice [matemáticas] 0 [/ matemáticas] y seguir aumentando mientras encontramos su correspondiente índice [matemáticas] derecha [/ matemáticas] hasta [matemáticas] izquierda \ ge derecha [ /matemáticas].

Nuestra respuesta se convierte en [matemáticas] \ suma \ límites_ {derecha> izquierda} ^ {} (derecha-izquierda) [/ matemáticas]
Donde la izquierda va de [matemática] 0,1,… [/ matemática] hasta [matemática] derecha \ le izquierda [/ matemática]

Aquí hay un código Ruby (lenguaje de programación) para esto:

def count_pairs(a,z) left = 0 right = a.length-1 count = 0 while right>left while (right > left) and (a[left]+a[right]>=z) right = right -1 end if (right > left) count = count + (right - left) end left = left + 1 end return 2*count end 

La respuesta a nuestro problema original es simplemente [matemática] 2 * {cuenta} [/ matemática] porque para cada par [matemática] (x, y) [/ matemática] tal que [matemática] x x [/ matemáticas]. Esto claramente toma [matemáticas] O (n) [/ matemáticas]

Algoritmo: ventana deslizante (compresión) y búsqueda binaria (una vez)
La matriz está ordenada a la derecha. Entonces el primero es el elemento más pequeño. Sea x

Mantenga un contador e inicialícelo en 0.
Busque (zx) en la matriz. Si no existe, descubra el elemento más grande <(zx).

• Estos dos son los puntos finales de la ventana. Actualice el contador a (Índice del elemento (zx) en la matriz). Esto significa que todos los valores de y menos que esto tienen x como combinación para que y + x
• Mantenga dos punteros i y j en x y zx (índices del paso 1)
• Ahora continúe este paso hasta que i y j se fusionen o la ventana se comprima
• Mueva i por 1. Mueva la j correspondiente hasta que la suma de los elementos en estos índices sea menor que z nuevamente. agregar (y index -x index al contador).

Análisis: aquí Una vez que se realiza la búsqueda binaria: O (logN). La ventana se comprime a cero> así que en el peor de los casos, i y j se mueven en un total por n. Aqui .

Complejidad total: O (N)

 
 pares de int (int arr [], int n, int z)
 {
       int x, y, i, j, contador = 0;
       j = BinarySearch (z-arr [0]); 
       / * Este es el punto final de la ventana.  Tenga en cuenta que la búsqueda proporciona un índice menos si el elemento no está allí> busqueda binaria de diseño según esa condición.  Se deja al interrogador * /
       i = 0; 
       mientras que (i <= j)
       {
              contador + = (ji);
              yo--;
             while (j> = i && arr [i] + arr [j]> = z) j--;  disminuir j hasta que su suma sea menor que z
       }
      printf ("Los pares totales son% d \ n", contador);
 }

Aquí no sirve de nada ir más allá del punto final ya que la x siempre aumenta y, por lo tanto, y debería disminuir para hacer su suma como Z o menos.

Sigue codificando
Diviértete 🙂