程序員面試題精選100題(61)-數對之差的最大值[算法]

時間:2019-09-22 編輯:范文亭

題目:在數組中,數字減去它右邊的數字得到一個數對之差。求所有數對之差的最大值。例如在數組{2, 4, 1, 16, 7, 5, 11, 9}中,數對之差的最大值是11,是16減去5的結果。

分析:看到這個題目,很多人的第一反應是找到這個數組的最大值和最小值,然后覺得最大值減去最小值就是最終的結果。這種思路忽略了題目中很重要的一點:數對之差是一個數字減去它右邊的數字。由于我們無法保證最大值一定位于數組的左邊,因此這個思路不管用。

于是我們接下來可以想到讓每一個數字逐個減去它右邊的所有數字,并通過比較得到數對之差的最大值。由于每個數字需要和它后面的O(n)個數字作減法,因此總的時間復雜度是O(n2)

解法一:分治法

通常蠻力法不會是最好的解法,我們想辦法減少減法的次數。假設我們把數組分成兩個子數組,我們其實沒有必要拿左邊的子數組中較小的數字去和右邊的子數組中較大的數字作減法。我們可以想象,數對之差的最大值只有可能是下面三種情況之一:(1)被減數和減數都在第一個子數組中,即第一個子數組中的數對之差的最大值;(2)被減數和減數都在第二個子數組中,即第二個子數組中數對之差的最大值;(3)被減數在第一個子數組中,是第一個子數組的最大值。減數在第二個子數組中,是第二個子數組的最小值。這三個差值的最大者就是整個數組中數對之差的最大值。

在前面提到的三種情況中,得到第一個子數組的最大值和第二子數組的最小值不是一件難事,但如何得到兩個子數組中的數對之差的最大值?這其實是原始問題的子問題,我們可以遞歸地解決。下面是這種思路的參考代碼:

int MaxDiff_Solution1(int numbers[], unsigned length)

{

    if(numbers == NULL || length < 2)

        return 0;

 

    int max, min;

    return MaxDiffCore(numbers, numbers + length - 1, &max, &min);

}

 

int MaxDiffCore(int* start, int* end, int* max, int* min)

{

    if(end == start)

    {

        *max = *min = *start;

        return 0x80000000;

    }

本文已影響
相關文章
大亨pk10计划苹果版