找出數組元素之間的最小差異

Question

我有一個整數數組，其中有一些有限數量的值。我的工作是找出數組中任意兩個元素之間的最小差異。

認爲數組包含

4, 9, 1, 32, 13 

這裏的區別是最小的4和1之間，因此答案是3

應該怎麼解決這個問題的算法。另外，我不知道爲什麼，但我覺得使用樹木可以相對容易地解決這個問題。可以這樣做嗎？

Answer 1

最小差異將是排序順序中連續對之間的差異之一。排序的數組，經過對相鄰數字的尋找最小的區別：

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

我想對他們O(nlogn)堆然後彈出一個接一個，並得到之間的最小差值我彈出的每個元素。最後我會有最小的差異。但是，可能有更好的解決方案。

Answer 3

你可以採取的，你正在考慮整數 做出線性算法的事實優勢：

1. 第一遍： 計算最大和最小
2. 第二遍： 分配布爾數組（最大 - 最小+ 1），假初始化， ，並將數組中的每個值更改爲（真值 - 最小）值的布爾數組條目。

Answer 4

這其實是中的closest-pair問題的重述。 https://en.wikipedia.org/wiki/Closest_pair_of_points_problem http://www.cs.umd.edu/~samir/grant/cp.pdf

由於維基百科的文章援引低於所指出的，這個問題的最好的決策樹模型也運行在Ω(nlogn)時間。

Answer 5

雖然所有的答案都是正確的，但我想顯示負責n log n運行時間的底層算法。 分而治之找到兩點之間的最小距離或找到一維平面中最近點的方式。

的一般算法：

• 設M =中值（S）。
• 將S分成S1，S2在m處。
• δ1=最近對（S1）。
• δ2=最近對（S2）。
• δ12是整個切割的最小距離。
• 返回δ= min（δ1，δ2，δ12）。

這是我在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}`);