Encontrar la diferencia mínima entre elementos en una matriz

Question

Tengo una matriz de enteros con un número finito de valores. Mi trabajo es encontrar la diferencia mínima entre dos elementos en la matriz.

consideran que la matriz contiene

4, 9, 1, 32, 13 

Aquí la diferencia es mínima entre 4 y 1 y así respuesta es 3.

¿Cuál debe ser el algoritmo de abordar este problema. Además, no sé por qué, pero creo que al usar árboles, este problema se puede resolver de manera relativamente fácil. ¿Se puede hacer eso?

Answer 1

La diferencia mínima será una de las diferencias entre los pares consecutivos en el orden ordenado. Ordenar la matriz, e ir a través de los pares de números adyacentes en busca de la más pequeña diferencia:

int[] a = new int[] {4, 9, 1, 32, 13}; 
Arrays.sort(a); 
int minDiff = a[1]-a[0]; 
for (int i = 2 ; i != a.length ; i++) { 
    minDiff = Math.min(minDiff, a[i]-a[i-1]); 
} 
System.out.println(minDiff); 

This prints 3.

Answer 2

me los pondría en un montón en O(nlogn) continuación, el pop, uno por uno y obtener la diferencia mínima entre cada elemento que exploto Finalmente tendría la mínima diferencia. Sin embargo, podría haber una mejor solución.

Answer 3

Puede aprovechar el hecho de que usted está considerando enteros para hacer un algoritmo lineal:

1. Primer paso: calcular el máximo y el mínimo
2. Segundo paso: asignar una matriz booleana de longitud (max - min + 1), inicialización falsa, y cambie el valor (valor - min) th a verdadero para cada valor en la matriz
3. Tercer paso: calcule las diferencias entre los índices del verdadero las entradas valoradas de la matriz booleana.

Answer 4

Esto es en realidad una reexpresión del problema closest-pair en one-dimension. https://en.wikipedia.org/wiki/Closest_pair_of_points_problem http://www.cs.umd.edu/~samir/grant/cp.pdf

Como el artículo de Wikipedia se cita más adelante señala, el mejor modelo de árbol de decisión de este problema también se ejecuta en Ω(nlogn) tiempo.

Answer 5

Si bien todas las respuestas son correctas, quería mostrar el algoritmo subyacente responsable del tiempo de ejecución n log n. El divide y conquista forma de encontrar la distancia mínima entre los dos puntos o encontrar los puntos más cercanos en un plano 1-D.

El algoritmo general:

• Let m = mediana (S).
• Divide S en S1, S2 en m.
• δ1 = Par más cercano (S1).
• δ2 = Par más cercano (S2).
• δ12 es la distancia mínima a través del corte.
• Retorno δ = min (δ1, δ2, δ12).

Este es un ejemplo que creé en Javascript:

// Points in 1-D 
 
var points = [4, 9, 1, 32, 13]; 
 

 
var smallestDiff; 
 

 
function mergeSort(arr) { 
 
    if (arr.length == 1) 
 
    return arr; 
 

 
    if (arr.length > 1) { 
 
    let breakpoint = Math.ceil((arr.length/2)); 
 
    // Left list starts with 0, breakpoint-1 
 
    let leftList = arr.slice(0, breakpoint); 
 
    // Right list starts with breakpoint, length-1 
 
    let rightList = arr.slice(breakpoint, arr.length); 
 

 
    // Make a recursive call 
 
    leftList = mergeSort(leftList); 
 
    rightList = mergeSort(rightList); 
 

 
    var a = merge(leftList, rightList); 
 
    return a; 
 
    } 
 
} 
 

 
function merge(leftList, rightList) { 
 
    let result = []; 
 
    while (leftList.length && rightList.length) { 
 
    // Sorting the x coordinates 
 
    if (leftList[0] <= rightList[0]) { 
 
     result.push(leftList.shift()); 
 
    } else { 
 
     result.push(rightList.shift()); 
 
    } 
 
    } 
 

 
    while (leftList.length) 
 
    result.push(leftList.shift()); 
 

 
    while (rightList.length) 
 
    result.push(rightList.shift()); 
 

 
    let diff; 
 
    if (result.length > 1) { 
 
    diff = result[1] - result[0]; 
 
    } else { 
 
    diff = result[0]; 
 
    } 
 

 
    if (smallestDiff) { 
 
    if (diff < smallestDiff) 
 
     smallestDiff = diff; 
 
    } else { 
 
    smallestDiff = diff; 
 
    } 
 
    return result; 
 
} 
 

 
mergeSort(points); 
 

 
console.log(`Smallest difference: ${smallestDiff}`);