Sprawdzanie minimalnej różnicy między elementami w tablicy

Question

Mam tablicę całkowitą z pewną skończoną liczbą wartości. Moim zadaniem jest znaleźć minimalną różnicę między dowolnymi dwoma elementami w tablicy.

Uważają, że tablica zawiera

4, 9, 1, 32, 13 

Tutaj różnica jest minimalna między 4 i 1, a więc odpowiedź brzmi 3.

Jaki powinien być algorytm podejść do tego problemu. Ponadto, nie wiem dlaczego, ale czuję, że używając drzew, ten problem można rozwiązać stosunkowo łatwiej. Czy to możliwe?

Answer 1

Minimalna różnica będzie jedną z różnic pomiędzy kolejnymi parami w posortowanej kolejności. Posortować tablicę, i przejść przez pary sąsiednich numerów szuka najmniejszej różnicy:

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

chciałbym umieścić je w sterty w O(nlogn) następnie pop jeden po drugim i uzyskać minimalną różnicę pomiędzy każdy element, który wyskakuję. W końcu będę miał minimalną różnicę. Jednak może być lepsze rozwiązanie.

Answer 3

Można skorzystać z faktu, że bierzesz pod uwagę całkowite dokonać liniowego algorytmu:

1. Pierwsze przejście: obliczyć maksymalną i minimalną
2. drugim przejściu: przeznaczyć logiczną tablicę o długości (max - min + 1), false initialized, i zmień wartość (value - min) na true dla każdej wartości w tablicy
3. Trzeci przebieg: obliczyć różnice między indeksami true wartościowane wpisy tablicy boolowskiej.

Answer 4

Jest to w rzeczywistości przekształcenie problemu closest-pair w one-dimension. https://en.wikipedia.org/wiki/Closest_pair_of_points_problem http://www.cs.umd.edu/~samir/grant/cp.pdf

Ponieważ artykuł Wikipedia cytowane poniżej wskazuje najlepszy model drzewa decyzji tego problemu działa również w Ω(nlogn) czasie.

Answer 5

Podczas gdy wszystkie odpowiedzi są poprawne, chciałem pokazać podstawowy algorytm odpowiedzialny za n log n czas pracy. dzieli i pokonuje sposób znajdowania minimalnej odległości między dwoma punktami lub znajdowania najbliższych punktów w płaszczyźnie 1-D.

ogólny algorytm:

• m = mediana (S).
• Podziel S na S1, S2 na m.
• δ1 = Najbliższa para (S1).
• δ2 = Najbliższa para (S2).
• δ12 to minimalna odległość w poprzek cięcia.
• Powrót δ = min (δ1, δ2, δ12).

Oto przykład stworzyłem w 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}`);