encontrar trillizos

Question

Sé que este tipo de pregunta se ha publicado anteriormente, pero quiero hablar de algo nuevo. Por lo tanto, lo estoy publicando.

Dada una matriz no ordenada de enteros, encuentre todos los trillizos que satisfagan x^2 + y^2 = z^2.

Por ejemplo, si matriz dada es - 1, 3, 7, 5, 4, 12, 13 La respuesta debería ser - 5, 12, 13 y 3, 4, 5

I se sugiere a continuación algo con complejidad O (n^2) -

• Ordene la matriz en orden descendente. - O (nlogn)
• cuadrado cada elemento. - O (n)

Ahora se reduce el problema de encontrar todos los trillizos (a, b, c) en una matriz ordenada tal que a = b + c.

El entrevistador insistía en una solución mejor que O (n^2).

He leído 3SUM problem on Wikipedia, que enfatiza que el problema se puede resolver en O (n + ulogu) si los números están dentro del rango [-u, u] suponiendo que la matriz se puede representar como un vector de bits. Pero no puedo obtener una idea clara de más explicaciones.

¿Puede alguien ayudarme a comprender lo que está pasando con un buen ejemplo?

Answer 1

Primero de todos. Encontrar todos los trillizos en el peor de los casos es O(n^3). Supongamos que tiene n=3k números. K de ellos son 3, k son 4 y K son 5.

3,....,3,4,....,4,5,.....5 

Hay k^3 = n^3/27 = O(n^3) tales tripletes. Solo imprimirlos toma el tiempo O(n^3).

A continuación se explicará de 3SUM problema en la forma:

hay números s_1, ..., s_n cada uno de ellos en el rango de [-u;u]. ¿Cuántos trillizos a,b,c hay que a+b=c?

1. transforming. Obtenga 2 * u números a_-u, ..., a_0, a_1, ... a_u. a_i es la cantidad de números s_j, que s_j = i. Esto se hace en O(n+u)

2. res = a_0 * sum(i=-u..u, i=/=0, C(a_i, 2)) + C(a_0,3)a_0 = 0

3. construir un polinomio P(x) = sum(i = -u...u, a_i*x^(i+u).

4. Encuentra Q(x) = P(x)*P(x) usando FFT.

5. Nota que Q(x) = sum(i=-2u..2u, b_i*x^(i+2*u)), donde b_i es el número de pares de s_u, s_k que s_u+s_k = i (Esto incluye el uso mismo número dos veces).

6. Para todos incluso i do b_i = b_i - a_(i/2). Esto eliminará usar el mismo número dos veces.

7. Sumar todos b_i*a_i/2 - agregar a res.

Ejemplo: para ser más simple, asumiré que rango para números es [0..u] y no utilizar cualquier + u en potencias de x. Supongamos que tenemos los números 1,2,3 - a_0 = 0, a_1 = 1, a_2 = 1, a_3 = 1

• res = 0

• P(x) = x + x^2 + x^3

• Q(x) = x^2 +2x^3+3x^4+2x^5+x^6

• Después de restar b_2 = 0, b_3 = 2, b_4 = 2, b_5 = 2, b_6 = 0

• res += 0*1/2 + 2*1/2 + 2*0/2 + 2*0/2 + 6*0/2 = 1

Answer 2

Otra posibilidad (¿quién puede sondear la mente de un entrevistador) habría que volver a escribir la ecuación como:

x^2 + y^2 = z^2 
x^2 = z^2 - y^2 = (z-y)(z+y) 

Si sabíamos que la factorización prima de x^2 a continuación, podríamos simplemente iterar a través de todas las factorizaciones posibles en un par de números p, q (con p < q) y calcular

x^2 = p.q = (z-y)(z+y) 
p+q = (z-y)+(z+y) = 2z 
q-p = (z+y)-(z-y) = 2y 
z = (p+q)/2 
y = (q-p)/2 

Por lo tanto, dada una factorización x^2 = p.q, podemos calcular los valores de z e y. Al poner todos los valores enteros en un conjunto, podemos verificar cada respuesta posible en el tiempo O (1) (por cheque) al observar si esos valores z, y están en el conjunto (teniendo cuidado de que también se detecten los valores negativos) .

Wikipedia says que un entero elegido al azar tiene sobre log (n) divisores por lo que esto debería tomar alrededor de n.log (n) suponiendo que puede hacer la factorización lo suficientemente rápido (por ejemplo, si sabía que todos los enteros eran menos de un millón precomputar una matriz del factor más pequeño para cada número entero).