Tengo una serie de números con tamaño uniforme, aquí está mi tarea:
a) Deseche 2 elementos cualquiera de la matriz. b) Luego empareje los elementos y calcule la suma de las diferencias entre los elementos del par tal que la suma sea mínima.
Ejemplo:
array size even say 8. array elements : 1,3,4,6,3,4,100,200 Ans: 5Explicación:
Aquí eliminaré 100 y 200, ya que emparejarlos me da una diferencia de (200 - 100) = 100. Entonces, los elementos restantes son [1,3,4,6,3,4] Los pares con suma mínima son: (1 3 ), (4 3), (6 4). = |3-1| = 2, |4-3|=1,|6-4| = 2. Entonces Suma = 2 + 1 + 2 = 5
Ejemplo:
array size even say 4. array elements : 1,50,51,60 Ans: 1Explicación : aquí eliminaré 1 y 60 para obtener la suma mínima. Entonces, los elementos restantes son [50, 51], igual que los adyacentes [50 51] = 1. Mi código fallará en este caso y devolverá 49.
¿Cómo lograr esto en Java?
Intenté ordenar los elementos de esta manera, pero este no es el enfoque correcto para todo tipo de entradas.
public static int process(int[] a) { int n = a.length; int n1 = n/2-1; Arrays.sort(arr); int sum = 0; for(int i=0; i<n1*2; i+=2) { sum += a[i+1] - a[i]; } return sum; }En este tipo de problema, el problema real es encontrar un buen algoritmo.
este post insistirá en este aspecto. Se proporciona un código C++ al final solo para ilustrarlo.
Está claro que debemos comenzar por ordenar la matriz.
Una solución consiste en calcular iterativamente tres sumas, donde
sum0 is the minimum sum assuming no element has been removed sum1 is the minimum sum assuming one element has been removed sum2 is the minimum sum assuming two elements has been removed Durante este proceso, el código debe mantener el rastro del último elemento disponible para calcular una diferencia, una para cada suma ( i_dispo0, i_dispo1, i_dispo2 ).
Principios:
- if sum1 > sum0: sum1 is replaced by sum0 - if sum2 > sum1: sum2 is replaced by sum1 Complejidad: O(n logn) para ordenar, O(n) para la fase de optimización.
Código:
El algoritmo se ilustra con el siguiente código simple en C++.
Debe ser fácil de entender.
Salida: 5 1 2 0 2
#include <iostream> #include <vector> #include <algorithm> int min_sum_diff (std::vector<int>& arr) { int n = arr.size(); if (n%2) exit (1); std::sort (arr.begin(), arr.end()); int sum0 = 0, sum1 = arr[n-1] - arr[0] + 1, sum2 = arr[n-1] - arr[0] + 1; int i_dispo0 = -1, i_dispo1 = -1, i_dispo2 = -1; for (int i = 0; i < n; ++i) { int sum0_old = sum0; int sum1_old = sum1; if (i_dispo0 == -1) { i_dispo0 = i; } else { sum0 += arr[i] - arr[i_dispo0]; i_dispo0 = -1; } if (i_dispo1 == -1) { i_dispo1 = i; } else { int add = arr[i] - arr[i_dispo1]; if (sum0_old < sum1 + add) { sum1 = sum0_old; i_dispo1 = i; } else { sum1 += add; i_dispo1 = -1; } } if (i_dispo2 == -1) { i_dispo2 = i; } else { sum2 += arr[i] - arr[i_dispo2]; i_dispo2 = -1; } if (sum2 > sum1_old) { sum2 = sum1_old; i_dispo2 = i; } //std::cout << i << " : " << sum0 << " " << sum1 << " " << sum2 << '\n'; } return sum2; } int main() { std::vector<std::vector<int>> examples = { {1, 3, 4, 6, 3, 4, 100, 200}, // -> 5 {1, 50, 51, 60}, // -> 1 {1,2,100,200,400,401}, // -> 2 {1, 10, 10, 20, 30, 30}, // -> 0 {1, 10, 11, 20, 30, 31} // -> 2 }; for (std::vector<int>& arr: examples) { int sum = min_sum_diff (arr); std::cout << sum << '\n'; } return 0; }El OP establece que en el primer paso se pueden eliminar dos elementos cualquiera de la matriz. Si ese es el caso, a partir de entonces el problema es igual a encontrar una coincidencia ponderada máxima en un gráfico. Véase, por ejemplo, esta explicación.
Las implementaciones de algoritmos para este problema se pueden encontrar aquí (con una buena explicación del problema en sí) en Boost (C++). En Java, que es lo que busca el OP, se pueden encontrar varios algoritmos aquí , en la biblioteca JGraphT .
Tenga en cuenta que, por lo general, los algoritmos se escriben para un peso máximo, mientras que el OP busca un peso mínimo. La estrategia para proyectar el gráfico de esta forma es:
Para ilustrar, en el ejemplo original, después de eliminar 100 y 200, los siguientes elementos permanecen en la matriz: 1,3,4,6,3,4. Cada elemento representa un borde (digamos A, B, C, D, E, F). El vértice AB tiene peso -2, el vértice AC tiene peso -3, y así sucesivamente. Si aplicamos un algoritmo para encontrar una coincidencia máxima con un peso máximo en este gráfico, corresponderá a un peso mínimo en el problema de OP.
Probé la solución publicada anteriormente para varias otras entradas, pero no era válida para diferentes conjuntos de entradas. Por lo tanto, estoy publicando un enfoque diferente que funciona bien para diferentes conjuntos de entradas.
Ordenar la matriz en orden ascendente
Tome una variable para inicializar la minimum sum a la sum of difference of the last two and first two elements de la matriz.
Inicie un loop ( excluding the last two elements of array ).
Cada ejecución de bucle debe calculate the sum of difference of pairs y compare it with minimum sum para actualizar su valor si la ejecución actual del bucle tiene el total mínimo.
Por lo tanto, estaremos cubriendo todos los pares después de que terminemos con la ejecución del ciclo y obtendremos la suma mínima.
public static int findMinSum(int[] a){ Arrays.sort(a); int minSum=a[1]-a[0]+a[a.length-1]-a[a.length-2]; for (int i=0,j=a.length-2;i<a.length/2 && j<a.length;i++,j++){ int sum=0; int counter=i; while(counter<j){ sum=sum+(a[counter+1]-a[counter]); counter+=2; } if(sum < minSum){ minSum=sum; } } return minSum; } - original array={95,98,100,101,102,110} - initialize minimum sum to (110-102)+(98-95) = 11 - loop stages : - (98-95) +(101-100) = 4 (new minimum sum=4) - (100-98)+(102-101) = 3 (new minimum sum=3) - (101-100)+(110-102) = 9 (minimum sum remains 3)He probado más el siguiente conjunto de entradas: -
{1,3,3,4,4,6,100,200} {1,50,51,60} {1,2,100,200,400,401} {1,2,100,300,400,401} {1,2,3,4,4,6,100,200} {95,98,100,101,102,401}Informe si se producen discrepancias en algún conjunto de entrada.