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

emacsnw 发表于 2006-11-14 11:22

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


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

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

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

aloneme_live 发表于 2006-11-14 11:25

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


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

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


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

chzht001 发表于 2006-11-14 11:26

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


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

这种情况是没考虑到

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

splitflag 发表于 2006-11-14 11:30

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

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

同意！

chzht001 发表于 2006-11-14 11:37

哎，:roll:

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

aloneme_live 发表于 2006-11-14 11:48

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

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

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

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

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

cMEr 发表于 2006-11-14 11:50

回复 55楼 splitflag 的帖子

follow

:em11:

flw2 发表于 2006-11-14 12:20

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

naker 发表于 2006-11-14 12:36

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

seaway 发表于 2006-11-14 12:47

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秒用来编译运行

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