Dada una matriz de números enteros, encuentre los elementos máximo y mínimo utilizando comparaciones mínimas.
Solución ingenua
Simplemente podemos iterar a través de la matriz y comparar dos veces con cada elemento para obtener el mínimo y el máximo. Esto conduce a 2n comparaciones.
//sudo code max = A[0], min = A[0] for each i in A if A[i]>max then max = A[i] if A[i]<min then min = A[i] |
public static void minmax0(int[] a) { if (a == null || a.length < 1) return; int min = a[0]; int max = a[0]; for (int i = 1; i <= a.length - 1; i++) { if (max < a[i]) { max = a[i]; } if (min > a[i]) { min = a[i]; } } System.out.println("min: " + min + "nmax: " + max); } |
# de comparaciones: 2 (n-1).
Aparentemente, deberíamos hacerlo mejor que esto.
Mejor solución 1
public static void minmax1(int[] a) { if (a == null || a.length < 1) return; int min, max; // if only one element if (a.length == 1) { max = a[0]; min = a[0]; System.out.println("min: " + min + "nmax: " + max); return; } if (a[0] > a[1]) { max = a[0]; min = a[1]; } else { max = a[1]; min = a[0]; } for (int i = 2; i <= a.length - 1; i++) { if (max < a[i]) { max = a[i]; } else if (min > a[i]) { min = a[i]; } } System.out.println("min: " + min + "nmax: " + max); } |
# de comparaciones en el peor de los casos: 1 + 2 (n-2) = 2n -1
# de comparaciones en el mejor de los casos: 1 + (n – 2) = n -1
# de comparaciones en promedio: 1.5n -1
En la implementación anterior, el peor de los casos ocurre cuando los elementos se ordenan en orden descendente, porque cada vez que max es mayor que un[i] y la segunda condición siempre se ejecuta. El mejor caso ocurre cuando los elementos se ordenan en orden ascendente, porque cada vez max es menor que un[i] y la segunda condición nunca se ejecuta.
Mejor solución 2
El número de comparaciones se puede reducir comparando pares primero:
public static void minmax2(int[] a) { if (a == null || a.length < 1) return; int min, max; // if only one element if (a.length == 1) { max = a[0]; min = a[0]; System.out.println("min: " + min + "nmax: " + max); return; } if (a[0] > a[1]) { max = a[0]; min = a[1]; } else { max = a[1]; min = a[0]; } for (int i = 2; i <= a.length - 2;) { if (a[i] > a[i + 1]) { min = Math.min(min, a[i + 1]); max = Math.max(max, a[i]); } else { min = Math.min(min, a[i]); max = Math.max(max, a[i + 1]); } i = i + 2; } if (a.length % 2 == 1) { min = Math.min(min, a[a.length - 1]); max = Math.max(max, a[a.length - 1]); } System.out.println("min: " + min + "nmax: " + max); } |
# de comparaciones cuando n es par: 1 + 3 * ((n-2) / 2) = 1.5n-2.
# de comparaciones cuando n es impar: 1 + 3 * ((n-3) / 2) + 2 = 1.5n
Mejor solución 3
class Pair { int min; int max; } public class Solution { public static Pair getMinMax(int arr[], int low, int high) { Pair result = new Pair(); Pair left = new Pair(); Pair right = new Pair(); // if there is only one element if (low == high) { result.max = arr[low]; result.min = arr[low]; return result; } // if there are two elements if (high == low + 1) { if (arr[low] > arr[high]) { result.max = arr[low]; result.min = arr[high]; } else { result.max = arr[high]; result.min = arr[low]; } return result; } // if there are more than 2 elements int mid = (low + high) / 2; left = getMinMax(arr, low, mid); right = getMinMax(arr, mid + 1, high); if (left.min < right.min) result.min = left.min; else result.min = right.min; if (left.max > right.max) result.max = left.max; else result.max = right.max; return result; } public static void main(String[] args) { int a1[] = { 3, 4, 2, 6, 8, 1, 9, 12, 15, 11 }; Pair result = getMinMax(a1, 0, a1.length - 1); System.out.println("Min: " + result.min); System.out.println("Max: " + result.max); } } |
# de comparaciones:
T(1) = 0 T(2) = 1 T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 ~ 2(T(n/2) + 2 = 1.5n -2
Conclusión
Mediante la optimización, podemos reducir el número de comparación de 2n del enfoque ingenuo a 1,5n.
