華為面試題(8分鐘寫出代碼)

susesuse

原帖由 hawk2012 于 2006-11-15 10:56 發(fā)表
假設(shè)數(shù)組a中的所有元素用a1, a2, a3, ..., an表示， 數(shù)組b中的為b1,b2,b3,...,bn表示。
那么令result = (a1 + a2 + a3+ ... + an) - (b1 + b2 + b3 + ... + bn)
                   = (a1 + a2 + a3+ ... + an) ...

所以 result = Sum - 2(b1 + b2 + b3 + ... + bn)
要使 result 為最小，只需要(b1 + b2 + b3 + ... + bn)為最大。

呵呵，沒有考慮Sum - 2(b1 + b2 + b3 + ... + bn)可能為負(fù)數(shù)？

hawk2012

是的， 是這個(gè)題目出的有問題，應(yīng)該說是a b數(shù)組和的差的絕對值最小才對，不然我的算法就是最小的。

susesuse

原帖由 hawk2012 于 2006-11-15 11:08 發(fā)表
是的， 是這個(gè)題目出的有問題，應(yīng)該說是a b數(shù)組和的差的絕對值最小才對，不然我的算法就是最小的。

確實(shí)您的想法很有新意，一般人想不到，呵呵。

laowolf

hawk2012的算法是正確滴?........................................你們肯定?
(b1 + b2 + b3 + ... + bn)為最大,那么結(jié)果就是最小的n個(gè)數(shù)減最大的n 個(gè)數(shù),這樣還能做出差最小..............................................................................................................?

hawk2012

原帖由 laowolf 于 2006-11-15 11:17 發(fā)表
hawk2012的算法是正確滴?........................................你們肯定?
(b1 + b2 + b3 + ... + bn)為最大,那么結(jié)果就是最小的n個(gè)數(shù)減最大的n 個(gè)數(shù),這樣還能做出差最小................................... ...

是負(fù)數(shù)，當(dāng)然是最小的。取絕對值是最大。

laowolf

呵呵無語了......

moyan80

O2O2...驚呆菜鳥無數(shù)……

cMEr

個(gè)人覺得 xmyth 的比較合理些

求得天人驚現(xiàn)，以正視聽。

:em11:

dalianpansky

為啥沒人評論我的想法呢？唉！

x2

如果要求a-b最小, 將a和b聯(lián)合成一個(gè)數(shù)組， 然后從小到大排序不行嗎？