Intuición
Primero abordé este problema escribiendo una matriz de ejemplo, digamos: 3, -2, -5, 18. Llamaré a estos elementos A, B, C, D, respectivamente.
Luego, manualmente pasé por el proceso de encontrar la suma de las diferencias absolutas para todos los pares para A (por ejemplo, (A, B), (A, C), (A, D)). Esa suma es:
- Cómo reconocer un problema como un problema de programación dinámica
- ¿Cuál es el enfoque algorítmico para este problema de hackerrank?
- ¿Cuáles son los algoritmos necesarios para resolver un cubo de rubics?
- ¿Qué algoritmo (s) de aprendizaje automático es el mejor para la regresión no lineal con un número limitado de datos?
- Cómo entender la solución óptima
| BA | + | CA | + | DA |
Mi deseo era que pudiera ignorar los signos de valor absoluto y reescribir la expresión como:
(BA) + (CA) + (DA)
que es lo mismo que:
(B + C + D) – 3A
Quería escribir la expresión en este formulario porque se puede calcular en [math] \ Theta (1) [/ math] tiempo después del tiempo de preprocesamiento [math] \ Theta (n) [/ math] usando sumas de prefijo.
Desafortunadamente, no podemos ignorar los signos de valor absoluto … a menos que la siguiente condición sea verdadera: B, C y D son mayores o iguales que A.
Cuando esta condición es verdadera, entonces la expresión anterior funciona. Afortunadamente, podemos ordenar la entrada para asegurarnos de que la condición anterior sea siempre cierta.
Algoritmo
Eso nos deja con el siguiente algoritmo:
- Ordene la matriz en orden ascendente ([matemática] O (n \ lg n) [/ matemática] tiempo).
- Calcule sumas de prefijos para la matriz ([matemática] \ Theta (n) [/ matemática] tiempo).
- Itere a través de la matriz (índice i) y calcule la suma de la diferencia absoluta para todos los pares a partir de la matriz [i] usando la fórmula: (prefixSums [n – 1] – prefixSums [i]) – (array [i] * (n – i – 1)) ([matemáticas] \ Theta (n) [/ matemáticas] tiempo)
- Devuelve la suma de las sumas de diferencia absoluta ([matemática] \ Theta (1) [/ matemática] hora)
La complejidad general del tiempo de ejecución es [matemática] O (n \ lg n) [/ matemática] tiempo. Si la entrada ya está ordenada, el algoritmo se ejecuta en tiempo [matemático] \ Theta (n) [/ matemático]. No estoy seguro de si este es el algoritmo más eficiente … puede haber un algoritmo [matemático] \ Theta (n) [/ matemático].
La complejidad general del espacio es [matemática] \ Theta (n) [/ matemática].
Código Java
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
import java.util.Arrays; public class AbsoluteDifferenceSum {
public static void main(String[] args) {
int[] array = { 3, -2, -5, 18 };
int absoluteDifferenceSum = findAbsoluteDifferenceSum(array); System.out.println(absoluteDifferenceSum);
} public static int findAbsoluteDifferenceSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array cannot be null or empty!");
} int n = array.length;
int[] arrayCopy = new int[n]; System.arraycopy(array, 0, arrayCopy, 0, n);
Arrays.sort(arrayCopy); int[] prefixSums = new int[n];
prefixSums[0] = arrayCopy[0]; for (int i = 1; i < n; ++i) {
prefixSums[i] = prefixSums[i - 1] + arrayCopy[i];
} int absoluteDifferenceSum = 0; for (int i = 0; i < n; ++i) {
int size = n - i - 1;
absoluteDifferenceSum += (prefixSums[n - 1] - prefixSums[i]) - (arrayCopy[i] * size);
} return absoluteDifferenceSum;
}
}
