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

undiedphoenix

感觉挺简单啊，这么长时间还有回复。1算出俩个数组和 的差值 2.将差值除以2（每次交换差值会缩小2倍）3.找到小于差值的最近的交换。
例如 a {1 2 3 4 } b{6 7 8 9}
一、suma =10 sumb=30   (sumb-suma)/2 =10
9 -1 =8 <10 交换 a{9 2 3 4} b{6 7 8 1}
二、suma =18 sumb=22   (sumb-suma)/2 =2
8 最小差4 ；7最小差3 ；6最小差2
正好交换6 和4 即可
a{9 2 3 6} b{4 7 8 1}
三、 suma = sumb =20

kangxukang

分析：
        当前数组a和数组b的和之差为
        A = sum(a) - sum(b)

        a的第i个元素和b的第j个元素交换后，a和b的和之差为
        A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
           = sum(a) - sum(b) - 2 (a - b[j])
           = A - 2 (a - b[j])
        设x = a - b[j]

        |A| - |A'| = |A| - |A-2x|

        假设A > 0,

        当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,

        如果找不到在(0,A)之间的x，则当前的a和b就是答案。

        所以算法大概如下：

        在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
上面的分析过程是网上找来的，这里说明下为什么是要接近A/2? <总体思想：一元二次方程求最值>

|A| - |A'| = |A| - |A-2x|

这是交换a和b[j]之后的表达式，交换a和b[j]的条件是：交换之后的 |A'| 比 |A|小，也即交换之后两数组元素和的差减小了。即|A| - |A'| > 0, 等价于|A| - |A-2x| > 0

==> |A| > |A-2x|   ==>两边取平方去掉绝对值符号，x*x - Ax<0， 令f(x) = x*x - Ax ，求f(x)小于零的极值，正好是在x = A/2处，当A>0时，在区间(0, A/2)之间

逼近A/2；当当A>0时，在区间(A/2, 0)之间逼近A/2。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------
实现的代码自己去网上搜去。

另外，“先整体排序，再交叉取数”这种方法是不正确的，比如排序之后，第一个最大的放到一个数组里面，第二个和第三个的数的和如果比第一个最大的数小很多，那么第二个，第三个都要放到同一个数组里面。交叉取数就不对了。

liu877153987

回复 31# greensky_34

数组a,数组b，然后a.b.数组里元素全部排序后存放在数组c中。数组a、b依次取一个值并比较大小，然后再取一个值比较大小，此时数组a若满足两次大于或者小于数组b，则交换第二次所取得元素。这样就可以啦。

dd8924

无聊翻个老贴,我的思路是:
1:2个数组元素组个新数组并排序
2:先把最大的数丢到一个数组里
3:开始循环,分别计算每个数组的和,倒序把新数组的元素丢到和较小的那个数组里.
欢迎指正.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARR_LEN                (5)
#define ARR_AREA        (100)

static int *g_pArra = NULL, *g_pArrb = NULL;

static int arrInit (const int **ppAddr, int len, int size)
{        
        int nRet = 0;

        if (NULL == ppAddr || !len || !size) {
                perror ("bad param!");
                nRet = -1;
                return nRet;
        }
        *ppAddr = calloc (len, size);
        if (NULL == ppAddr)        {
                perror ("ppAddr calloc err!");
                nRet = -1;
                return nRet;        
        }
        return nRet;
}

static int arrElementGet (void)
{
        int nElement = 0;

        //srand ((int)time(NULL));
        nElement = rand () % ARR_AREA;
        //printf ("get new element [%d]\n", nElement);

        return nElement;
}

static arrFill (int len)
{
        int nRet = 0;
        int i = 0;
        for (i = 0; i < len; ++i)        {
                g_pArra = arrElementGet();
                g_pArrb = arrElementGet();
        }

        return nRet;
}

static int arrPrint (const int *pArrd, int len)
{
        int i = 0;
        for (i = 0; i < len; ++i)        {
                printf ("%d ", pArrd);
        }
        printf ("\n");
}

static int arrCmp(const void *a, const void *b)
{
     return(*(int *)a-*(int *)b);
}

static int arrSumGet (const int *pAddr, int len)
{
        int i = 0, sum = 0;
        for (i = 0; i < len; ++i)        {
                sum += pAddr;
        }
        return sum;
}

int main (int argc, char *argv[])
{
        int nRet = 0;
        int i = 0, j = 0, k = 0;
        int *pArrTmp = NULL;
        int nTatolSum = 0;
        int nAvg = 0;
        int sumA = 0, sumB = 0;

do {
        nRet = arrInit (&g_pArra, ARR_LEN, sizeof(int));
        if (nRet)        {
                perror ("g_pArra arrInit error!!!");
                break;
        }

        nRet = arrInit (&g_pArrb, ARR_LEN, sizeof(int));
        if (nRet)        {
                perror ("g_pArrb arrInit error!!!");
                break;
        }

        nRet = arrFill (ARR_LEN);

        printf ("arr a:");
        arrPrint (g_pArra, ARR_LEN);
        printf ("arr b:");
        arrPrint (g_pArrb, ARR_LEN);

        // make a new array
        nRet = arrInit (&pArrTmp, ARR_LEN * 2, sizeof(int));
        if (nRet)        {
                perror ("pArrTmp arrInit error!!!");
                break;
        }
        // fill element from array a and b
        for (i = 0; i < ARR_LEN * 2; ++i)        {
                pArrTmp = (ARR_LEN <= i) ? g_pArrb[i - ARR_LEN] : g_pArra;
        }
        printf ("arr tmp:");
        arrPrint (pArrTmp, ARR_LEN * 2);
        
        // sort
        qsort (pArrTmp, ARR_LEN * 2, sizeof (int), arrCmp);

        printf ("\nsort arr tmp:");
        arrPrint (pArrTmp, ARR_LEN * 2);

        nTatolSum = arrSumGet (pArrTmp, ARR_LEN * 2);
        nAvg = nTatolSum / 2;
        printf ("nTatolSum=%d nAvg=%d \n", nTatolSum, nAvg);

        memset (g_pArra, 0x0, ARR_LEN*4);
        memset (g_pArrb, 0x0, ARR_LEN*4);

        // fill the max element
        g_pArra[ARR_LEN - 1] = pArrTmp[ARR_LEN*2 - 1];
        j = ARR_LEN - 2; k = ARR_LEN - 1;
        for (i = ARR_LEN * 2 - 2; i > 0; --i)        {
                sumA = arrSumGet (g_pArra, ARR_LEN);
                sumB = arrSumGet (g_pArrb, ARR_LEN);
                //arrPrint (g_pArra, ARR_LEN);
                //arrPrint (g_pArrb, ARR_LEN);
                printf ("pArrTmp=%d sumA=%d, sumB=%d \n", pArrTmp, sumA, sumB);
                if (sumA >= sumB)        {
                        g_pArrb[k] = pArrTmp;
                        --k;
                }
                else        {
                        g_pArra[j] = pArrTmp;
                        --j;
                }
        }
        printf ("after change arr a:");
        arrPrint (g_pArra, ARR_LEN);
        printf ("after change arr b:");
        arrPrint (g_pArrb, ARR_LEN);
        sumA = arrSumGet (g_pArra, ARR_LEN);
        sumB = arrSumGet (g_pArrb, ARR_LEN);
        printf ("sumA=%d, sumB=%d diff=%d \n", sumA, sumB, sumA-sumB);
}while (0);
        if (g_pArra)        {
                free (g_pArra);
        }
        if (g_pArrb)        {
                free (g_pArrb);
        }

        printf ("app exit!\n");
        return nRet;
}

cao627

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #define N 7
   
4. 
   
5. int sumd(int a[N], int b[N]);
   
6. 
   
7. int main()
   
8. {
   
9.     int a[] = {2,6,7,9,22,11,34};
   
10.     int b[] = {55,35,64,28,12,5,8};
    
11.     int i, j, n, m;
    
12.     int x, y;
    
13.     int t;
    
14.     int tmp;
    
15.     int f;
    
16.     while ( 1) {
    
17.         f = 1;
    
18.         x = sumd(a, b)/2;                                                    //求得两数组和的差值的中点，每一轮数组a和b元素的交换应尽可能靠近这个中点。
    
19.         t = abs(x);
    
20.         printf("%d\n", x);
    
21.         for (i=0; i<N; i++){
    
22.             for (j=0; j<N; j++){
    
23.                 y = a[i] - b[j];
    
24.                 if (abs(x-y) < abs(x) && abs(x-y) <  t){       //遍历数组a中的每一个元素与数组b中的每一个元素做差值，每一轮遍历求得最合适的两数做交换。
    
25.                     t = abs(x-y);
    
26.                     m = i;
    
27.                     n = j;
    
28.                     f = 0;
    
29.                 }
    
30.             }
    
31.         }
    
32.         if (f) break;
    
33.         tmp = a[m];
    
34.         a[m] = b[n];
    
35.         b[n] = tmp;
    
36. 
    
37.     }
    
38. 
    
39.     for (i=0; i<N; i++){
    
40.     printf("a[%d]=%d b[%d]=%d\n", i,a[i],i,b[i]);
    
41.     }
    
42.     return 0;
    
43. }
    
44. 
    
45. int sumd(int a[], int b[])
    
46. {
    
47.     int i, s=0;
    
48.     for (i=0; i<N; i++){
    
49.         s += a[i] - b[i];
    
50.     }
    
51.     return s;
    
52. }
    
53. 
    
54.                                                                            

复制代码

zoujh2000

整体排序、交叉分配的误区就不分析了，太简单。
看到很多根据sum(a)-sum(b)交换元素的例子，这些方法对下面的数组仍然是错的：
数组a {1, 20, 30, 40}
数组b {10, 10, 25, 44}
原因是那些方法只考虑互换一个元素以减小差值，但有时候得互换一组（多个）元素。
比如上例中已无可换的单个元素，差值为2。但将 a 的 {1, 20} 与 b 的 {10， 10} 互换，差值为0才是正确结果。

gameas

我还没看完贴呢，再看发现自己错了。

forxy

有两个贪心的人a和b,瓜分偶数堆钱，你觉得他们会怎么做？总有一个先选，比如a,他选最大的，然后轮到b,不用说，b也选最大的。剩下一个问题，后面的怎么分？第三轮，上帝觉得b不爽了，于是让b先选，第四轮，上帝觉得a或者b不爽，让不爽的人先选…直到选完为止。
其实第一轮选完后，后面的问题有点像递归了。