论坛 › C/C++ › 华为面试题(8分钟写出代码)

la.lune 发表于 2006-11-13 10:55

放到一个临时数组里排序后，两头取，分别存在a,b里

同意~

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

cugb_cat 发表于 2006-11-13 11:06

将两个数组都放到一个数组里,然后对这个数组从大到小进行排序,然后将排好序的数组的第一个元素减第二个元素,第三个元素减第四个元素.....一直到第2n-1减第2n个元素,然后求和就得到最小的差值了.排序可以用stdlib.h中的qsort函数,该函数提供的是快速排序算法.

ccjjhua 发表于 2006-11-13 11:42

把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最小的，b先取次小的，
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。策略是，已取得的所有元素之和大的来取C中剩下元素中的最小者。如此反复，直到取完。每次都是a,b各取一个。

forrestgang 发表于 2006-11-13 13:58

原帖由 zhhui2000 于 2006-11-13 07:54 发表
先各自排序,再交叉存放较大无素


这样应该不行:shock:

forrestgang 发表于 2006-11-13 13:59

原帖由 yg 于 2006-11-13 10:17 发表
全部加起来除2，然后试算


面试官说了不能用枚举

hydonlee 发表于 2006-11-13 14:14

同意楼上.
先对两个数组计算各自的和, 然后计算出sum_a - sum_b, 然后开始LOOP, 找到能使sum_a与sum_b逼近的值, 交换.
直到没有交换为止.

s5unty 发表于 2006-11-13 15:43

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

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

yg 发表于 2006-11-13 17:00

可以不用穷举，递归、回溯都行啊

namtso 发表于 2006-11-13 17:16

我相信，这个题在8分钟内能写出代码来的人，绝对是大大的牛人。

我觉得应该这样：
a和b 分别求出累加和，得出累加和的差c1，然后循环查找找a中的某个元素a，使得a与b中的某个元素b交换之后，得出一个新的累加和之差c2，并且|c2|<|c1|，如果找到这样的一个元素a，则与b交换，然后进入下一轮的递归运算。如果找不到这样的一个元素，则说明此时两个数组的累加和之差已经最小。

mill888 发表于 2006-11-13 17:29

8分钟就能写出正确方法的人，建议就不要去华为了，应当去更好的公司。
招聘中，建议华为公司应当定好自己的位。

查看完整版本: 华为面试题(8分钟写出代码)