- 相關(guān)推薦
程序員精選面試題100題
題目：在數(shù)組中，數(shù)字減去它右邊的數(shù)字得到一個(gè)數(shù)對(duì)之差。求所有數(shù)對(duì)之差的最大值。例如在數(shù)組{2, 4, 1, 16, 7, 5, 11, 9}中，數(shù)對(duì)之差的最大值是11，是16減去5的結(jié)果。
分析：看到這個(gè)題目，很多人的第一反應(yīng)是找到這個(gè)數(shù)組的最大值和最小值，然后覺得最大值減去最小值就是最終的結(jié)果。這種思路忽略了題目中很重要的一點(diǎn)：數(shù)對(duì)之差是一個(gè)數(shù)字減去它右邊的數(shù)字。由于我們無(wú)法保證最大值一定位于數(shù)組的左邊，因此這個(gè)思路不管用。
于是我們接下來(lái)可以想到讓每一個(gè)數(shù)字逐個(gè)減去它右邊的所有數(shù)字，并通過(guò)比較得到數(shù)對(duì)之差的最大值。由于每個(gè)數(shù)字需要和它后面的O(n)個(gè)數(shù)字作減法，因此總的時(shí)間復(fù)雜度是O(n2)。
解法一：分治法
通常蠻力法不會(huì)是最好的解法，我們想辦法減少減法的次數(shù)。假設(shè)我們把數(shù)組分成兩個(gè)子數(shù)組，我們其實(shí)沒有必要拿左邊的子數(shù)組中較小的數(shù)字去和右邊的子數(shù)組中較大的數(shù)字作減法。我們可以想象，數(shù)對(duì)之差的最大值只有可能是下面三種情況之一：(1)被減數(shù)和減數(shù)都在第一個(gè)子數(shù)組中，即第一個(gè)子數(shù)組中的數(shù)對(duì)之差的最大值;(2)被減數(shù)和減數(shù)都在第二個(gè)子數(shù)組中，即第二個(gè)子數(shù)組中數(shù)對(duì)之差的最大值;(3)被減數(shù)在第一個(gè)子數(shù)組中，是第一個(gè)子數(shù)組的最大值。減數(shù)在第二個(gè)子數(shù)組中，是第二個(gè)子數(shù)組的最小值。這三個(gè)差值的最大者就是整個(gè)數(shù)組中數(shù)對(duì)之差的最大值。
在前面提到的三種情況中，得到第一個(gè)子數(shù)組的最大值和第二子數(shù)組的最小值不是一件難事，但如何得到兩個(gè)子數(shù)組中的數(shù)對(duì)之差的最大值?這其實(shí)是原始問(wèn)題的子問(wèn)題，我們可以遞歸地解決。下面是這種思路的參考代碼：
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;
}
int* middle = start + (end - start) / 2;
int maxLeft, minLeft;
int leftDiff = MaxDiffCore(start, middle, &maxLeft, &minLeft);
int maxRight, minRight;
int rightDiff = MaxDiffCore(middle + 1, end, &maxRight, &minRight);
int crossDiff = maxLeft - minRight;
*max = (maxLeft > maxRight) ? maxLeft : maxRight;
*min = (minLeft < minRight) ? minLeft : minRight;
int maxDiff = (leftDiff > rightDiff) ? leftDiff : rightDiff;
maxDiff = (maxDiff > crossDiff) ? maxDiff : crossDiff;
return maxDiff;
}
在函數(shù)MaxDiffCore中，我們先得到第一個(gè)子數(shù)組中的最大的數(shù)對(duì)之差leftDiff，再得到第二個(gè)子數(shù)組中的最大數(shù)對(duì)之差rightDiff。接下來(lái)用第一個(gè)子數(shù)組的最大值減去第二個(gè)子數(shù)組的最小值得到crossDiff。這三者的最大值就是整個(gè)數(shù)組的最大數(shù)對(duì)之差。
解法二：轉(zhuǎn)化成求解子數(shù)組的最大和問(wèn)題
接下來(lái)再介紹一種比較巧妙的解法。如果輸入一個(gè)長(zhǎng)度為n的數(shù)組numbers，我們先構(gòu)建一個(gè)長(zhǎng)度為n-1的輔助數(shù)組diff，并且diff[i]等于numbers[i]-numbers[i+1](0<=i)。如果我們從數(shù)組diff中的第i個(gè)數(shù)字一直累加到第j個(gè)數(shù)字(j > i)，也就是diff[i] + diff[i+1] + … + diff[j] = (numbers[i]-numbers[i+1]) + (numbers[i + 1]-numbers[i+2]) + ... +(numbers[j] numbers[j+ 1]) = numbers[i] numbers[j + 1]。
分析到這里，我們發(fā)現(xiàn)原始數(shù)組中最大的數(shù)對(duì)之差(即numbers[i] numbers[j + 1])其實(shí)是輔助數(shù)組diff中最大的連續(xù)子數(shù)組之和。我們?cè)诒鞠盗械牟┛偷牡?篇《求子數(shù)組的最大和》中已經(jīng)詳細(xì)討論過(guò)這個(gè)問(wèn)題的解決方法�；谶@個(gè)思路，我們可以寫出如下代碼：
int MaxDiff_Solution2(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int* diff = new int[length - 1];
for(int i = 1; i < length; ++i)
diff[i - 1] = numbers[i - 1] - numbers[i];
int currentSum = 0;
int greatestSum = 0x80000000;
for(int i = 0; i < length - 1; ++i)
{
if(currentSum <= 0)
currentSum = diff[i];
else
currentSum += diff[i];
if(currentSum > greatestSum)
greatestSum = currentSum;
}
[] diff;
return greatestSum;
}
解法三：動(dòng)態(tài)規(guī)劃法
既然我們可以把求最大的數(shù)對(duì)之差轉(zhuǎn)換成求子數(shù)組的最大和，而子數(shù)組的最大和可以通過(guò)動(dòng)態(tài)規(guī)劃求解，那我們是不是可以通過(guò)動(dòng)態(tài)規(guī)劃直接求解呢?下面我們?cè)囍脛?dòng)態(tài)規(guī)劃法直接求數(shù)對(duì)之差的最大值。
我們定義diff[i]是以數(shù)組中第i個(gè)數(shù)字為減數(shù)的所有數(shù)對(duì)之差的最大值。也就是說(shuō)對(duì)于任意h(h < i)，diff[i]≥number[h]-number[i]。diff[i](0≤i)的最大值就是整個(gè)數(shù)組最大的數(shù)對(duì)之差。
假設(shè)我們已經(jīng)求得了diff[i]，我們?cè)撛趺辞蟮胐iff[i+1]呢?對(duì)于diff[i]，肯定存在一個(gè)h(h < i)，滿足number[h]減去number[i]之差是最大的，也就是number[h]應(yīng)該是number[i]之前的所有數(shù)字的最大值。當(dāng)我們求diff[i+1]的時(shí)候，我們需要找到第i+1個(gè)數(shù)字之前的最大值。第i+1個(gè)數(shù)字之前的最大值有兩種可能：這個(gè)最大值可能是第i個(gè)數(shù)字之前的最大值，也有可能這個(gè)最大值就是第i個(gè)數(shù)字。第i+1個(gè)數(shù)字之前的最大值肯定是這兩者的較大者。我們只要拿第i+1個(gè)數(shù)字之前的最大值減去number[i+1]，就得到了diff[i+1]。
int MaxDiff_Solution3(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int max = numbers[0];
int maxDiff = max - numbers[1];
for(int i = 2; i < length; ++i)
{
if(numbers[i - 1] > max)
max = numbers[i - 1];
int currentDiff = max - numbers[i];
if(currentDiff > maxDiff)
maxDiff = currentDiff;
}
return maxDiff;
}
在上述代碼中，max表示第i個(gè)數(shù)字之前的最大值，而currentDiff表示diff[i] (0≤i)，diff[i]的最大值就是代碼中maxDiff。
解法小結(jié)
上述三種代碼，雖然思路各不相同，但時(shí)間復(fù)雜度都是O(n)(第一種解法的時(shí)間復(fù)雜度可以用遞歸公式表示為T(n)=2(n/2)+O(1)，所以總體時(shí)間復(fù)雜度是O(n))。我們也可以注意到第一種方法是基于遞歸實(shí)現(xiàn)，而遞歸調(diào)用是有額外的時(shí)間、空間消耗的(比如在調(diào)用棧上分配空間保存參數(shù)、臨時(shí)變量等)。第二種方法需要一個(gè)長(zhǎng)度為n-1的輔助數(shù)組，因此其空間復(fù)雜度是O(n)。第三種方法則沒有額外的時(shí)間、空間開銷，并且它的代碼是最簡(jiǎn)潔的，因此這是最值得推薦的一種解法。
【程序員面試題100題】相關(guān)文章：
2014年MBA面試題目大綱100題07-11
程序員面試題精選07-12
入門級(jí)PHP程序員面試題07-09
100個(gè)最權(quán)威的招聘面試題及回答解析07-11
誰(shuí)有近幾年華為和中興公司的Java程序員面試題07-11
c面試題08-04
華為面試題07-11
「MySQL」經(jīng)典面試題07-11
面試題與技巧07-12
采購(gòu)面試題07-11