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

la.lune

放到一個(gè)臨時(shí)數(shù)組里排序后，兩頭取，分別存在a,b里[/quote]

同意~

[ 本帖最后由 la.lune 于 2006-11-13 10:56 編輯 ]

cugb_cat

將兩個(gè)數(shù)組都放到一個(gè)數(shù)組里,然后對(duì)這個(gè)數(shù)組從大到小進(jìn)行排序,然后將排好序的數(shù)組的第一個(gè)元素減第二個(gè)元素,第三個(gè)元素減第四個(gè)元素.....一直到第2n-1減第2n個(gè)元素,然后求和就得到最小的差值了.排序可以用stdlib.h中的qsort函數(shù),該函數(shù)提供的是快速排序算法.

ccjjhua

把a(bǔ),b 2數(shù)組的元素放到數(shù)組3（2n大小） 中進(jìn)行排序，
a 先取最小的，b先取次小的，
然后根據(jù)a,b已取元素和的大小來(lái)決定誰(shuí)來(lái)取剩下元素中最小的。策略是，已取得的所有元素之和大的來(lái)取C中剩下元素中的最小者。如此反復(fù)，直到取完。每次都是a,b各取一個(gè)。

forrestgang

原帖由 zhhui2000 于 2006-11-13 07:54 發(fā)表
先各自排序,再交叉存放較大無(wú)素

這樣應(yīng)該不行

forrestgang

原帖由 yg 于 2006-11-13 10:17 發(fā)表
全部加起來(lái)除2，然后試算

面試官說(shuō)了不能用枚舉

hydonlee

同意樓上.
先對(duì)兩個(gè)數(shù)組計(jì)算各自的和, 然后計(jì)算出sum_a - sum_b, 然后開(kāi)始LOOP, 找到能使sum_a與sum_b逼近的值, 交換.
直到?jīng)]有交換為止.

s5unty

在1/4炷香之后，我意識(shí)到如果a = {1,2,3}; b = {0,0,999}。那么先排序后交叉取就不行了

[ 本帖最后由 s5unty 于 2006-11-13 15:46 編輯 ]

yg

可以不用窮舉，遞歸、回溯都行啊

namtso

我相信，這個(gè)題在8分鐘內(nèi)能寫(xiě)出代碼來(lái)的人，絕對(duì)是大大的牛人。

我覺(jué)得應(yīng)該這樣：
a和b 分別求出累加和，得出累加和的差c1，然后循環(huán)查找找a中的某個(gè)元素a[i]，使得a[i]與b中的某個(gè)元素b[j]交換之后，得出一個(gè)新的累加和之差c2，并且|c2|<|c1|，如果找到這樣的一個(gè)元素a[i]，則與b[j]交換，然后進(jìn)入下一輪的遞歸運(yùn)算。如果找不到這樣的一個(gè)元素，則說(shuō)明此時(shí)兩個(gè)數(shù)組的累加和之差已經(jīng)最小。

mill888

8分鐘就能寫(xiě)出正確方法的人，建議就不要去華為了，應(yīng)當(dāng)去更好的公司。
招聘中，建議華為公司應(yīng)當(dāng)定好自己的位。