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

cuicp

大侠们看这样可不可以：

1。先把两个数组相加，求平均数（a）。
2。在数组中取出和平均数差最小的一个或多个，如果是一个就分在一组，如果是多个就平均分（奇数个和偶数个一样）。
3。把剩下的元素排序，一次取两个元素（升序或降序），算一下两个元素的和（b）与差（c），取（b－a）和（c－a）绝对值小的那个，如果（b－a）小，把两个元素都加到和小的那个组中去，如果（c－a）小，把b和c中大的那个加到元素和小的那一组，把b和c中小的那个加到数组和大的那一组。

例如：
1，3，5
平均数：3
取3，分为第一组，
取1，5,因为（（1＋5）－3） > （（5－1）－3）,把1分给和大的那组，也就是第一组，把5分给和小的那组，也就是第二组，因为其和为零。
这样，5－（1＋3）＝1

又例如：
1，5，10，15
平均数：7。75，
先取10，分为第一组，
然后取1，5，因为（7。75－（1＋5）） < （7。75－（5－1））,所以把1与5都分给数组和小的那组，也就是第二组，然后取15分给和小的那组，（因为只剩15了）
最后得到：（10＋1＋5）－15 ＝ 1
差最小。

类推：
1，2，3，4，5，6

分为：
3，1，2，5
4，6

差为：1

不知道这种分法怎么样？
大家参考一下！！

有不对的地方请高手指正！
谢谢！！

cuicp

原帖由 cMEr 于 2006-11-14 10:18 发表
取出所有，大小排序，
最大减最小，
取最接近差值的元素，
放在较小的一组，
直到最后。

论证中。。。。

这样好像不行，
比如：
1，2，3，4，5，6

结果是不是：
3，5，1
4，2，6

可是不是最佳方案。

cuicp

原帖由 seaway 于 2006-11-14 12:48 发表
t1＝a1的和＋a2的和；
结果数组＝空数组;
循环开始（所有的数组组合情况）
{
  t2=绝对值（新数组a-新数组b）;
  if( t2< t1)
  {
       t1=t2;
       结果数组CLEAR（）；
       结果数组ADD（t2 ...

高，实在是高，
呵呵，把所有的组合都试一遍，差最小的组合记下来，
不就行了？
不过要麻烦一下计算机大哥了，
可以算一下一共有多少种组合，
如果两个数组元素和是n，那么全面覆盖的次数大概是：
n+n*(n-1)+n*(n-1)*(n-2)...

这个对不对？要怎么算呢？大学的课程都忘光了！
如果要短时间内完成的话，这可能是个好办法！

cuicp

n+n*(n-1)+n*(n-1)*(n-2)...

这个好像算错了，是不是要除个2？

排列组合，忘光了！

：）

cuicp

原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
       = sum(a) - sum(b) - 2 (a - b[j]) ...

想法很好呀，又有数学证明，但是什么时候会
找不到（0,A）之间的x呢？
比如：
1，2，3，4，5，12
最佳方案好像是：
4，5，3
1，2，12

那么0<（3－2）<(15-12)

好像不行呀？
是不是要改进一下结束的条件？
我考虑的对不对？
高手看看！
谢谢！！

cuicp

原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的

在你说的这个例子里，已经满足了我所提出的结束条件

前面我假设了A>0 (如果A不大于0，对换一下就好了)

所以这里a = {1,2,12}; b = {4,5,3};

x=a-b[j]

所有的x ...

哦，明白了，如果(sum(a) - sum(b)) > (a -b[j]) > 0的话，也就是数组a的和比数组b的和大，
而数组b中有比数组a中小的元素，如果把a和b[j]交换，就可以把数组a和数组b的差缩小，又因为
(sum(a) - sum(b)) > (a -b[j]) ，所以交换后不会出现sum(a) < sum(b)的情况。这样循环调整后，
当整体上sum(a)  > sum(b))时，局部上（数组元素）无法交换了，也就是无法找到符合条件的x了。

呵呵，本人天生比较笨，要想一想才能明白！

谢谢xmyth的解释！