Aquí hay una solución con complejidad O (N).
En primer lugar, si tomamos la primera matriz ordenada en orden creciente y la segunda matriz ordenada en orden decreciente, tales permutaciones nos darán una respuesta óptima. Puede leer el comentario de Arjun Arul para obtener una explicación de por qué funciona: cuando la primera matriz se ordena en orden creciente, después de mejorar la segunda matriz de forma iterativa, terminará con la segunda matriz ordenada en orden decreciente.
Por lo tanto, queremos ordenar dos matrices e invertir una de ellas … Bueno, es imposible lograr una complejidad mejor que NlogN para exactamente esta idea. Intentemos modificarlo un poco.
- ¿La programación a nivel del sistema se ha vuelto obsoleta?
- ¿Cuáles son las debilidades del descenso de gradiente?
- ¿Por qué y cómo son importantes los algoritmos en nuestra vida diaria?
- He pensado en un algoritmo simple y cómo algunas empresas podrían usarlo. ¿Cómo puedo ganar dinero con eso?
- ¿Cuál es el mejor libro para aprender algoritmos y estructuras de datos en Java para principiantes?
¿Cómo se ve la solución óptima? Hay algún prefijo, para el cual a [i] b [i], por lo que tenemos que tomar a [i] con más y b [i] con menos.
Tratemos de dividir todos los elementos en dos grupos según el signo que deberían tener en la suma resultante.
Imaginemos que ya conocemos el valor de a [i] yb [i] para nuestro “punto especial” (después de lo cual a [i] se vuelve más grande que b [i]) , y también todos a [i] y b [i ] son distintos. En este caso, sabemos que todos los valores de a [j] tal que a [j] <= a [i] se tomarán con signo menos (pertenecen a un prefijo, donde tenemos a [j] a [i] se tomará con un signo más. Buenas noticias: en tal caso, podemos resolver nuestro problema en O (N), porque para cada elemento podemos determinar su suma resultante al compararlo con un elemento especial de la matriz correspondiente. Malas noticias: no sabemos cómo encontrar valores para un punto crucial, además es posible que algunos elementos de nuestra matriz sean iguales.
Ahora algún algoritmo de selección debería ayudarnos. Puede usar cosas como el enésimo elemento para encontrar una mediana de matriz en O (N) y también reorganizarla de tal manera que todos los elementos a la izquierda de la mediana no sean más grandes que los elementos a la derecha. Vamos a aplicarlo para encontrar medianas de matrices a [] yb [] y compararlas. Con esta información, podemos determinar si el prefijo para el cual a [i] <= b [i] tiene una longitud de al menos N / 2 o es menor. Ahora supongamos que es más que N / 2. En este caso, podemos tomar el sufijo de nuestras matrices y encontrar medianas allí nuevamente (así sabremos que el “punto especial” es al menos 3 * N / 4 elementos desde el principio o en algún lugar entre N / 2 y 3 * N / 4 ; no olvide que para la segunda matriz estamos usando un comparador diferente para ordenar los elementos en orden decreciente) . Se puede hacer en operaciones N / 2, porque ahora estamos trabajando con matrices que son dos veces más cortas. Podemos continuar haciendo este tipo de búsqueda binaria para encontrar la posición exacta en la que a [i] se hace más grande que b [i]: tomará N + N / 2 + N / 4 + N / 8 + … = EN). También sabemos que en un momento dado todos los elementos de un [] a la izquierda desde nuestro punto especial no son más grandes que el elemento en una posición interesante, y todos los elementos a la derecha no son más pequeños que el elemento interesante. Por lo tanto, todos los elementos de un prefijo se tomarán con el signo menos, y todos los elementos de un sufijo se tomarán con el signo más 🙂 Y para b [], los elementos del prefijo se tomarán con un signo más, y los elementos del sufijo se tomarán con un signo menos .
