华为面试题(8分钟写出代码)

sunyu_bit

原帖由 yuxh 于 2006-11-13 20:20 发表

这个基本可行，但不是交叉存放较大元素，而是哪边的和小就一直放大元素，直到n，然后把剩下的扔到另一组中就ok了。

这个不保证找出的是最优解，可以交叉之后再做局部调整

glasslion

下意识就是DP
但8分钟绝对遍不好

glasslion

背包变形

程序c

顶一下这个强帖，到现在还没看完

tianhailong

回复 1# forrestgang


    先对a,b排序，再计算a,b的和sum，除以2，对排好序的a,b做归并
时间复杂度是N*Log(N)
之后取与 sum/2N最接近的值，可以是有折半查找，取一个值后，下一次取（sum-x）/2N-1,一次类推，
复杂度没考虑，应该是在N*Log(N) 之上，则得到的数组与sum/2查找最小，那么 剩下的数组与均值的差别也最小
总复杂的应高于N*log(N)

siyuweimxf

不但考程序，还考算法，还有数学了，数学学的不好。

siyuweimxf

排完序挨个放不行吧。

wenkai169

数组A和B，和分别为S1, S2 且 S1 > S2
让 d=S1-S2

A[m]-B[n]=dd
如果交换A[m]和b[n]，则S1-S2=d-2*dd

让这个值d-2*dd趋于零即可

于是在数组中找寻让这个值趋于零的交换元素（1个或N个）。这就成了动态规划的问题了。

siyuweimxf

想出个差不多的，先取出全部排序，a0放最大的c0，b0放次大的c1，然后算a0-b0是否大于c2，
大的话c2放b，否则放a，再算suma-sumb是否大于c3，是的话c3放b，否则放a，直到先把b放满，
剩下的就全放a中。

siyuweimxf

具体代码，改天试试，大概应该可以。