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

emacsnw

原帖由 chzht001 于 2006-11-13 19:05 发表


那是因为还没有全排序，全排序时再结合我的处理方法才能得出结果
两数组和之差最小不一定是零，因为有两数组的数个数相同的约束

正确的处理应是先找出最大的和第二大的分别放入两个数组，然后再找除去这两 ...

这样是不对的，比如最大的元素如果大到超过其他所有元素的和，那么显然它所在的那个数组其他的n-1个元素应该是所有2n个元素里面最小的。

aloneme_live

原帖由 chzht001 于 2006-11-14 11:05 发表


那是因为还没有全排序，全排序时再结合我的处理方法才能得出结果
两数组和之差最小不一定是零，因为有两数组的数个数相同的约束

正确的处理应是先找出最大的和第二大的分别放入两个数组，然后再找除去这两 ...

如果数组为：
999,0,1
2,3,0
按照你这个算法就会有问题，依次得到：
999,3
1, 2,
0，0

chzht001

原帖由 emacsnw 于 2006-11-14 11:22 发表


这样是不对的，比如最大的元素如果大到超过其他所有元素的和，那么显然它所在的那个数组其他的n-1个元素应该是所有2n个元素里面最小的。

这种情况是没考虑到

[ 本帖最后由 chzht001 于 2006-11-14 11:30 编辑 ]

splitflag

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

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

同意！

chzht001

哎，

[ 本帖最后由 chzht001 于 2006-11-14 12:00 编辑 ]

aloneme_live

大家提出的任何算法，首先能够证明是正确的吗？我估计大部分都是在猜测而已。

这个题仅仅是想出正确的算法都不止需要8分钟，还说要8分钟内写出代码，痴人做梦啊。

谁要是能8分钟内想出正确的算法，我估计他都可以进微软研究院了，至于华为，他就别去了，浪费人才。

所以，大家先别忙着写程序，把算法说出来供大家讨论讨论就行，这个才能达到学习的目的。

[ 本帖最后由 aloneme_live 于 2006-11-14 12:01 编辑 ]

cMEr

follow

:em11:

flw2

8分钟,我觉得这个能写出来就非常8错了.

naker

不会是用人工神经网络来做吧，这样不用枚举，计算量为O(1),可8分钟写代码肯定没戏了。瞎说的，大家别拿臭鸡蛋砸我。

seaway

t1＝a1的和＋a2的和；
结果数组＝空数组;
循环开始（所有的数组组合情况）
{
  t2=绝对值（新数组a-新数组b）;
  if( t2< t1)
  {
       t1=t2;
       结果数组CLEAR（）；
       结果数组ADD（t2）；
  } else if(t2==t1)
  {
      结果数组ADD（t2）；
  }
}
return 结果数组;

如果有完善的数据结构开发包。3分钟就够了。其中30秒用来考虑，2分用来写程序，30秒用来编译运行