Dada una matriz sin clasificar, encuentre la diferencia máxima entre los elementos sucesivos en su forma ordenada.
Intenta resolverlo en tiempo / espacio lineal. Devuelve 0 si la matriz contiene menos de 2 elementos. Puede suponer que todos los elementos de la matriz son enteros no negativos y que encajan en el rango de enteros con signo de 32 bits.
Análisis
Podemos usar un algoritmo similar a un cubo para resolver este problema en el tiempo de O (n) y el espacio O (n). La idea básica es proyectar cada elemento de la matriz en una matriz de cubos. Cada balde rastrea los elementos máximos y mínimos. Finalmente, escaneando la lista de deseos, podemos obtener la brecha máxima.
La parte clave es obtener el intervalo:
From: interval * (num[i] - min) = 0 and interval * (max -num[i]) = n interval = num.length / (max - min)
El siguiente diagrama muestra un ejemplo.
Solución Java
class Bucket{ int low; int high; public Bucket(){ low = -1; high = -1; } } public int maximumGap(int[] num) { if(num == null || num.length < 2){ return 0; } int max = num[0]; int min = num[0]; for(int i=1; i<num.length; i++){ max = Math.max(max, num[i]); min = Math.min(min, num[i]); } // initialize an array of buckets Bucket[] buckets = new Bucket[num.length+1]; //project to (0 - n) for(int i=0; i<buckets.length; i++){ buckets[i] = new Bucket(); } double interval = (double) num.length / (max - min); //distribute every number to a bucket array for(int i=0; i<num.length; i++){ int index = (int) ((num[i] - min) * interval); if(buckets[index].low == -1){ buckets[index].low = num[i]; buckets[index].high = num[i]; }else{ buckets[index].low = Math.min(buckets[index].low, num[i]); buckets[index].high = Math.max(buckets[index].high, num[i]); } } //scan buckets to find maximum gap int result = 0; int prev = buckets[0].high; for(int i=1; i<buckets.length; i++){ if(buckets[i].low != -1){ result = Math.max(result, buckets[i].low-prev); prev = buckets[i].high; } } return result; } |
