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

iphonebabe

呵呵，这种题目很基础的

ww2000e

wang2666

看到15页就没继续看了。
自己做不出。
不过有几点问题，
1：数组个数问题 a[m],b[n]，处理后的个数不一定是m+n/2
2：数组的最大或最小两个数不一定分开
3：运算，排序过程中必须考虑大数问题
总之，这个问题不简单。

huxk

2n个数中 挑出n个 剩下就n个 分别就是2个几集合 怎么判断两个集合之差最小 岂不是要比较所有的可能状态 才能得知

不行 脑子不够用 罢了

johntsu

呵呵，实现不难，关键是思路。
我的思路是，定义数组a和数组b的副本，只不过是空的，我们将其取名为a1和b1。然后进入大小为数组大小为n的n次循环。第一次循环，找出数组a中最大的那个元素，放入数组a1的第一个格中；然后找出数组b中最小的那个元素，放入b1中。然后第二次循环，找出数组a中次最大的那个元素，放入数组a1的第二个格中；再找出数组b中次最小的那个元素，放入数组b1中。如此循环n次。最后再对a1和b1进行一次循环，如果a1的元素与b1中对应的元素大，则交换a1和b1的元素。如此循环n次。经过这两次循环之后，用a1中的元素之和减去b1中的元素之和，应该是最小差了。

不知道这样的思路对不对，还请大家给指点一下。3ks

scgywx

我的想法是，先将a与b数组合并然后排序，把最大的放入a，次大的放入b，依次从大到小循环，同时有两个变量suma与sumb分别计算a与b的和,当suma大于sumb时，将数据放入b,反之放入a(同时再次计算suma和sumb),直到数据分配完为止，如果有一个数组满时，剩下的数据全分到另一个数组。

cangt

穷举法，不排序

#include <stdio.h>
#include <math.h>
int a[] = {1,2,3,4,5};
int b[] = {6,7,8,9,10};
int main()
{   
    int i=0,j=0,dif=0,length=0,temp=0,mina,minb,ab;
    length = sizeof(a)/sizeof(int);
    for(i=0;i<length;i++){
        dif +=a[i]-b[i];                                
    }
    while(dif!=0)
    {   
        temp = abs(dif-(a[0]-b[0])*2);
        mina = 0;minb=0;mina=0;minb=0;
        for(i=0;i<length;i++)
        {
            for(j=0;j<length;j++)
            {
                ab = abs(dif-(a[i]-b[j])*2);
                if(ab<temp) {temp =ab; mina=i;minb=j;}
            }                        
        }
        if(abs(dif-(a[mina]-b[minb])*2)<abs(dif))
        {
             dif=dif-(a[mina]-b[minb])*2;
             temp = a[mina];
             a[mina] = b[minb];  
             b[minb] =  temp;  
                                       
        }else {break; printf("break");}
    }
    for(i=0;i<length;i++){
        printf("%d ",b[i]);                              
    }
    printf("\n");
    system("pause");
    return 0;   
}

wwwsq

思路：把两个数组加一个总和，然后问题退化为：从总和为2m的2n数组中，取出n个数字使其总和最接近m.

wwwsq

另一个思路：快速求取近似解，并支持动态的快速调整。

这应该是更接近现实的需求。

这个题目的背景猜测：交换机有两根线，如何平衡流量。则这个问题其实不需要精确解，近似解就可以了。

近似解的话，两个数组各记录一个当前总和，然后按照大小关系对两个数组进行lazy方式的调整。

如果题目的背景是我所猜测的，那么数组里面的数值其实是会快速变化的。那么如何快速的（或者以恰当频率的）进行调整，是很重要的需求；则我设计的这个求近似解的方法将好于任何求精确解的方法。

wwwsq

这个问题再扩大化：如何在N个数组之间平衡流量。

我上面的思路在这个背景下将更为有效。通过1/N的划分，把N*N的问题退化为两两之间的问题，近似解计算起来将毫无压力。