华为面试题(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秒用来编译运行

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)...

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

hiawen

应该是将两个数组作为一个数组进行冒泡排序。
a[0],b[0],a[1],b[1],......

scott_jia

原帖由 sithui 于 2006-11-13 09:33 发表
先整体排序，再交叉取数

英雄所见略同。

cuicp

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

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

排列组合，忘光了！

：）

chzht001

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

你做的很快，但计算机恐怕要累死了

dalianpansky

方案1.将a、b两个数组合成一个数组c（无需排序），清空a、b两数组。任取c中一个数据i，然后在c中查找与i差值最小的j，i放入a中，就放入b中，然后在c中去掉i和j；再次在c中任取一个数据i，然后在c中查找与i差值最小的j，i放入b中，j放入a中。（即奇数次取在数组a中，偶数次取在数组b中）。（注，两个n相加一定为偶数）

方案2. 将a、b两个数组合成一个数组c（2n个数据，无需排序），将所有数据相加，然后除以2，值记为i，然后随意组合n个数据相加，取和最接近i的组合为a，余下为b

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

crazy_li

原帖由 greensky_34 于 2006-11-14 00:28 发表


完整的程序是这样的，可以参考一下
[code]
#include <stdio.h>
#include <math.h>

#define N 10

void ary_init(int a[], int b[]){ //初始化数组
    int i;
    for (i=0; i<N; i ...

经过简单的验证，发现greensky_34的算法是对的啊。大家不要想得太复杂了。
{1,2,3}  {0,0,999}
{1,2,3,4,5,6} {7,8,9,10,11,12}

[ 本帖最后由 crazy_li 于 2006-11-14 14:39 编辑 ]

白色乌鸦

可以先做好个大致差不多的，再进行微调

zlqian

假设sum(a)>sum(b)
（1）选取a中第i个数，b中第j个数，满足ai-bj < sum(a)-sum(b)。交换ai和bj。
（2）重新计算sum(a)和sum(b)
（3）重复步骤1和2直到条件1不能再满足。
（4）输出a和b