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

syshunter

有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小

大家请看题目
试问a[] = { 1,2,3,4 };
b[] = { 3,4,5,6};

他们的和是固定数.那么无论怎么排序......差都一样.

这题主要考的是眼力和智力.你们都太次了.哈哈.

是你自己太次了吧。

私人杀手

原帖由 syshunter 于 2008-2-23 18:00 发表


是你自己太次了吧。

是你太次了.我没有说错啊.

Kevin_zqw

原帖由 chouy 于 2006-11-14 00:06 发表
1.  求和并除二, 记为 AVG
2.  用短的数组长度个的数字排列组合, 找最接近 AVG 的.
3.  把这几个数填入短数组, 其余填入长数组.

不知道这道题中是否要求输出换的步骤, 如果需要, 小 CASE. 不说了.

这个可行啊，排列组合。。

justkain

int temp[2*N]=....

Sort(Temp);

A:Get The Max();
B:Get The Max();
I=1;
While（I<N）
{
if(Sum(A) > Sum(B))
{
     IF(Sum(A)-Sum(B) > Max())
    {
        A:Get The Min();
        B:Get The Max();
    }
    else
    {
        B:Get The Max();
        if(Sum(B) < Sum(A))
        {
            A:Get The Min();
        }
        else if(Sum(B) - Sum(A) > Max())
        {
            A:Get The Max();
        }
        else
        {
          A:Get The Min();//可能存在问题
        }
    }
}
else
{
     原理同上，交换A，B角色
}
}

[ 本帖最后由 justkain 于 2008-7-6 19:22 编辑 ]

虑而后能得

呵呵 我觉得还是要找一个不变量，什么呢？就是两个数组的总和了设为sum，equ=sum/2;这是不变的，然后对两个数组的数循环取n个值，总和与equ差最小的放入一个数组，其余放入另一个数组。

虑而后能得

呵呵 另一种
a b合并为c【】
c[]排序，取最大的放入a，次大放入b，然后剩下的最大放入b，最小放入a，比较a当前和与b当前和，c中剩下的最大放入和小的，最小放入和大的，。。。。。直到分配完

wangsheng0415

Up Crazily!
不过题目是通过交换a,b数组中的数来操作的，所以还得处理下

wangsheng0415

先对a,b数组排序,
计算和之差offset;
if(sum(a)>sum(b))
寻找差不大于offset/2的最大值的两个数，交换

wangsheng0415

还有些情况漏了，要交换多个数使得偏差<=offset/2

虑而后能得

思想：
a b合并为c【】
c[]排序，取最大的放入a，次大放入b，然后剩下的最大放入b，最小放入a，比较a当前和与b当前和，c中剩下的最大放入和小的，最小放入和大的，。。。。。直到分配完
程序：
#include<stdio.h>
#include<stdlib.h>
int cmp ( const void *a , const void *b );
int main(void)
{
        int a[5] = {5,6,-11,2,3};
        int b[5] = {7,8,9,-15,1};
        int c[10];
        int i,suma = 0,sumb = 0;

        for(i = 0;i < 5;i++)
                c = a;
        for(i = 5;i < 10;i++)
                c = b[i - 5];
        qsort(c,10,sizeof(int),cmp);
       
        a[0] = c [9];
        b[0] = c[8];
        i=1;
        while(i<5)
        {
                suma += a[i-1];
                sumb += b[i-1];
                if(suma < sumb)
                {
                        a = c[9-i-1];
                        b = c[i-1];
                }
                else
                {
                        a = c[i-1];
                        b = c[9-i-1];
                }
                i++;

        }

        for(i = 0;i < 5;i++)
                printf("%3d",a);
        printf("\n");
        for(i = 0;i < 5;i++)
                printf("%3d",b);
        printf("\n");

        return 0;
       
}


int cmp ( const void *a , const void *b )
{
        return *(int *)a - *(int *)b;

}
结果：
9，-15，6，5，2
8，7，-11，1，3

呵呵 还是比较正确的，好像效率也不错啊。