華為面試題(8分鐘寫出代碼)

undiedphoenix

感覺挺簡單啊，這么長時間還有回復(fù)。1算出倆個數(shù)組和 的差值 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

分析：
        當(dāng)前數(shù)組a和數(shù)組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])
        設(shè)x = a - b[j]

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

        假設(shè)A > 0,

        當(dāng)x 在 (0,A)之間時，做這樣的交換才能使得交換后的a和b的和之差變小，x越接近A/2效果越好,

        如果找不到在(0,A)之間的x，則當(dāng)前的a和b就是答案。

        所以算法大概如下：

        在a和b中尋找使得x在(0,A)之間并且最接近A/2的i和j，交換相應(yīng)的i和j元素，重新計算A后，重復(fù)前面的步驟直至找不到(0,A)之間的x為止。
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
上面的分析過程是網(wǎng)上找來的，這里說明下為什么是要接近A/2? <總體思想：一元二次方程求最值>

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

這是交換a和b[j]之后的表達式，交換a和b[j]的條件是：交換之后的 |A'| 比 |A|小，也即交換之后兩數(shù)組元素和的差減小了。即|A| - |A'| > 0, 等價于|A| - |A-2x| > 0

==> |A| > |A-2x|   ==>兩邊取平方去掉絕對值符號，x*x - Ax<0， 令f(x) = x*x - Ax ，求f(x)小于零的極值，正好是在x = A/2處，當(dāng)A>0時，在區(qū)間(0, A/2)之間

逼近A/2；當(dāng)當(dāng)A>0時，在區(qū)間(A/2, 0)之間逼近A/2。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------
實現(xiàn)的代碼自己去網(wǎng)上搜去。

另外，“先整體排序，再交叉取數(shù)”這種方法是不正確的，比如排序之后，第一個最大的放到一個數(shù)組里面，第二個和第三個的數(shù)的和如果比第一個最大的數(shù)小很多，那么第二個，第三個都要放到同一個數(shù)組里面。交叉取數(shù)就不對了。

liu877153987

回復(fù) 31# greensky_34

數(shù)組a,數(shù)組b，然后a.b.數(shù)組里元素全部排序后存放在數(shù)組c中。數(shù)組a、b依次取一個值并比較大小，然后再取一個值比較大小，此時數(shù)組a若滿足兩次大于或者小于數(shù)組b，則交換第二次所取得元素。這樣就可以啦。

dd8924

無聊翻個老貼,我的思路是:
1:2個數(shù)組元素組個新數(shù)組并排序
2:先把最大的數(shù)丟到一個數(shù)組里
3:開始循環(huán),分別計算每個數(shù)組的和,倒序把新數(shù)組的元素丟到和較小的那個數(shù)組里.
歡迎指正.
#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;                                                    //求得兩數(shù)組和的差值的中點，每一輪數(shù)組a和b元素的交換應(yīng)盡可能靠近這個中點。
    
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){       //遍歷數(shù)組a中的每一個元素與數(shù)組b中的每一個元素做差值，每一輪遍歷求得最合適的兩數(shù)做交換。
    
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.                                                                            

復(fù)制代碼

zoujh2000

整體排序、交叉分配的誤區(qū)就不分析了，太簡單。
看到很多根據(jù)sum(a)-sum(b)交換元素的例子，這些方法對下面的數(shù)組仍然是錯的：
數(shù)組a {1, 20, 30, 40}
數(shù)組b {10, 10, 25, 44}
原因是那些方法只考慮互換一個元素以減小差值，但有時候得互換一組（多個）元素。
比如上例中已無可換的單個元素，差值為2。但將 a 的 {1, 20} 與 b 的 {10， 10} 互換，差值為0才是正確結(jié)果。

gameas

我還沒看完貼呢，再看發(fā)現(xiàn)自己錯了。

forxy

有兩個貪心的人a和b,瓜分偶數(shù)堆錢，你覺得他們會怎么做？總有一個先選，比如a,他選最大的，然后輪到b,不用說，b也選最大的。剩下一個問題，后面的怎么分？第三輪，上帝覺得b不爽了，于是讓b先選，第四輪，上帝覺得a或者b不爽，讓不爽的人先選…直到選完為止。
其實第一輪選完后，后面的問題有點像遞歸了。