es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Mínima diferencia absoluta entre dos arreglos, con la posibilidad de un reemplazo máximo.

Mínima diferencia absoluta entre dos arreglos, con la posibilidad de un reemplazo máximo.

10 Jun, 2023 Programación

Se te dan dos matrices de enteros a y b, ambas con la misma longitud.

Definimos la diferencia entre a y b como la suma de las diferencias absolutas de los elementos correspondientes:
  diferencia = |a[0] – b[0]| + |a[1] – b[1]| …

Puedes reemplazar un elemento de a con cualquier otro elemento de a.
Tu tarea es devolver la mínima diferencia posible entre a y b que se pueda lograr haciendo a lo sumo un reemplazo en a.
También puedes elegir dejar la matriz intacta.

Ejemplo

Para a = [1, 3, 5] y b = [5, 3, 1], la salida debe ser solution(a, b) = 4.

  • Si dejamos la matriz a intacta, la diferencia es: |1 – 5| + |3 – 3| + |5 – 1| = 8.
  • Si reemplazamos a[0] con a[1], obtenemos
    [3, 3, 5] y la diferencia es |3 – 5| + |3 – 3| + |5 – 1| = 6;
  • Si reemplazamos a[0] con a[2], obtenemos
    [5, 3, 5] y la diferencia es |5 – 5| + |3 – 3| + |5 – 1| = 4;
  • Si reemplazamos a[1] con a[0], obtenemos
    [1, 1, 5] y la diferencia es |1 – 5| + |1 – 3| + |5 – 1| = 10;
  • Si reemplazamos a[1] con a[2], obtenemos
    [1, 5, 5] y la diferencia es |1 – 5| + |5 – 3| + |5 – 1| = 10;
  • Si reemplazamos a[2] con a[0], obtenemos
    [1, 3, 1] y la diferencia es |1 – 5| + |5 – 3| + |1 – 1| = 4;
  • Si reemplazamos a[2] con a[1], obtenemos
    [1, 3, 3] y la diferencia es |1 – 5| + |3 – 3| + |3 – 1| = 6;

Así que la respuesta final es 4.

La solución debe tener una complejidad de O(n log n) como máximo.

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Algoritmo de Diferencia Mínima

    Dadas dos matrices de enteros a y b de igual longitud, encuentre la diferencia mínima posible entre a y b que se puede lograr realizando como máximo una sustitución en a. La diferencia entre a y b se define como la suma de las diferencias absolutas de los elementos correspondientes.

    Enfoque

    Para resolver este problema, podemos usar un enfoque ávido. Primero, calculamos la diferencia absoluta entre los elementos de a y b y los sumamos para obtener la diferencia inicial. Luego, intentamos minimizar esta diferencia revisando cada elemento de a y reemplazándolo con otro elemento de a. En cada paso, recalculamos la diferencia y llevamos un registro de la diferencia mínima que hemos encontrado hasta el momento.

    Si reemplazamos un elemento a[i] con otro elemento a[j], la nueva diferencia se puede calcular restando la diferencia absoluta entre a[i] y b[i] y sumando la diferencia absoluta entre a[j] yb[i].

    Pseudocódigo

    1. calcular la diferencia inicial entre a y b
2. establecer min_diff = diferencia inicial
3. para i en rango (len(a)):
4.     para j en rango (len(a)):
5.         original_diff = abs(a[i]-b[i]) + abs(a[j]-b[j])
6.         new_diff = abs(a[j]-b[i]) + abs(a[i]-b[j])
7.         si new_diff < original_diff:
8.             si new_diff < min_diff:
9.                 min_diff = new_diff
10. devolver min_diff

    El bucle externo en las líneas 3-10 itera sobre cada elemento de a, mientras que el bucle interno itera sobre todos los elementos de a. La diferencia original en la línea 5 es la diferencia entre a y b antes de cualquier reemplazo. La nueva diferencia en la línea 6 es la diferencia entre a y b después de reemplazar a[i] con a[j]. Si la nueva diferencia es menor que la diferencia original, actualizamos la diferencia mínima en la línea 9.

    Análisis de complejidad

    La complejidad temporal de este algoritmo es O(n^2), donde n es la longitud de la matriz a. Esto se debe a que tenemos un bucle anidado que itera sobre todos los pares de elementos en a. Sin embargo, podemos optimizar este algoritmo para que se ejecute en tiempo O(n log n) mediante la clasificación de la matriz a y la matriz b. Al hacer esto, podemos reducir el bucle interno de O(n) a O(log n) utilizando la búsqueda binaria para encontrar el elemento de reemplazo en la matriz a. La complejidad temporal total es O(n log n) debido al paso de clasificación.

Comments are closed.