如何在分而治之算法（一維最近對）完成其工作時返回正確的值？

Question

我需要找到最接近的整數數組對數。例如：如果我有{25,13,​​59,7,16}個數字，我的結果應該是| 13 - 16 | = 3.所以我嘗試使用分而治之算法來解決這個問題。但是，當我從子問題中獲得數字差異時，我無法存儲和比較它們。當我調試它時，我發現我的程序出錯了，但幾個小時卻找不到任何解決方案。

這裏是我的功能：

int closestPairs(int list[], int first, int last) 
{ 
    if (last - first == 1) 
     return 0; 
    else if (last - first == 2) 
     return abs(list[first] - list[last - 1]); 

    int median = (first + last)/2; 

    int left = closestPairs(list, first, median); 
    int right = closestPairs(list, median, last); 

    int temp = abs(list[first] - list[last - 1]); 

    if (abs(left - right) < temp) 
     temp = abs(left - right); 

    return temp; 
} 

這裏是驅動程序功能：

int main() 
{ 
    int list[] = { 34, 23, 48 , 4, 66, 69}; 
    int n = sizeof(list)/sizeof(int); 
    cout << closestPairs(list, 0, n) << endl; 

    return 0; 
} 

那麼，如何可以存儲從ABS（左 - 右）獲得的值，如果它不太看或大於下一個值？還是我錯了，做錯了什麼？提前致謝。

Answer 1

在我看來，在這種情況下，使用遞歸來查找解決方案並存儲與下一次迭代比較的值的概念是相反的概念。在遞歸函數中存儲一個用於比較的變量似乎會有點混亂（並且需要對代碼進行一些重要的重構）。我理解你的分而治之算法的想法是將大量的整數列入，並將其分成更小的列表，並允許儘可能好的答案在整個鏈中完成。這裏是（大多采用僞代碼）我看到基於代碼的工作方式：

int FindClosest(int list[],int first,int last) 
{ 
    if(number of elements in list == 2) 
    { 
     return (int2 - int1) 
    } 
    if(number of elements in list == 3){ 
    { 
     if((int3-int2)<(int2 - int2)) 
      return (int3-int2) 
     else 
      return (int2-int1) 
    } 
    if(number of elements in list >3) 
    { 
     subList1 = oneSubGroupofElements(list) 
     subList2 = anotherSubGroupofelements(list) 
     if(FindClosest(subList1)<FindClosest(subList2)) 
       return Findclosest(subList1) 
     else 
       return FindClosest(subList2) 
    } 
} 

沒有用這種方法，你可以看到有2組以上的元素列表的另一個問題，那是因爲你的結果依賴在成對的鄰居中，你必須考慮到你不能將列表分成兩半。例如：

int list[] = {1,4,5,9} 

，如果你簡單地拆分成列表兩個元素的兩個列表爲4和5之間的差異不會被認爲（這將是正確答案）會造成問題。您的子列表必須包含重疊，以便從FindClosest調用時至少有一個子列表返回5-4。

Answer 2

您必須在使用分治技術找到最接近的對之前對列表進行排序。因爲這消除了許多轉角情況。