Individuazione della differenza minima tra gli elementi in una matrice

Question

Ho una matrice intera con un numero finito di valori. Il mio compito è quello di trovare la differenza minima tra due elementi nell'array.

consideri che l'array contiene

4, 9, 1, 32, 13 

Qui la differenza è minima tra 4 e 1 e così risposta è 3.

Quale dovrebbe essere l'algoritmo di affrontare questo problema. Inoltre, non so perché, ma sento che usando gli alberi, questo problema può essere risolto relativamente più facilmente. Può essere fatto?

Answer 1

La differenza minima sarà una delle differenze tra le coppie consecutive in ordine. Ordinare l'array, e passare attraverso le coppie di numeri adiacenti cercando la più piccola differenza:

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

li metterebbe in un mucchio in O(nlogn) poi pop uno per uno e ottenere la differenza minima tra ogni elemento che pop. Finalmente avrei la minima differenza. Tuttavia, potrebbe esserci una soluzione migliore.

Answer 3

Si può approfittare del fatto che si stanno prendendo in considerazione gli interi per fare un algoritmo lineare:

1. Primo passaggio: calcolare il massimo e il minimo
2. Secondo passaggio: allocare una matrice booleana di lunghezza (max - min + 1), false inizializzato, e modifica il valore (valore - min) su vero per ogni valore nell'array
3. Terzo passo: calcola le differenze tra gli indici del valore vero voci valutate dell'array booleano.

Answer 4

Si tratta in realtà di una nuova versione del problema in one-dimension. https://en.wikipedia.org/wiki/Closest_pair_of_points_problem http://www.cs.umd.edu/~samir/grant/cp.pdf

Come l'articolo di Wikipedia ha citato di seguito sottolinea, il miglior modello di albero decisionale di questo problema viene eseguito anche in Ω(nlogn) tempo.

Answer 5

Mentre tutte le risposte sono corrette, volevo mostrare l'algoritmo sottostante responsabile del tempo di esecuzione n log n. Il divide e conquista il modo per trovare la distanza minima tra i due punti o trovare i punti più vicini in un piano 1-D.

L'algoritmo generale:

• Sia m = mediana (S).
• Dividere S in S1, S2 a m.
• δ1 = Coppia più vicina (S1).
• δ2 = Coppia più vicina (S2).
• δ12 è la distanza minima attraverso il taglio.
• Ritorno δ = min (δ1, δ2, δ12).

Ecco un esempio che ho creato in 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}`);