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

norlan

/*
解法假設(shè)：

1、假設(shè)存在數(shù)組a[n],b[n],且Sum(a[n]) < Sum(b[n]);

2、假設(shè)在數(shù)組a[n]與b[n]中，不存在元素a[i],使Sum(a[n]) < Sum(b[n])，且Sum(a[n])的值比上次求和的值大，則數(shù)組Sum(a[n])與數(shù)組Sum(b[n])
的差值最小。



*/


算法：

Sum(數(shù)據(jù)類型 *p, int n)//數(shù)組n的求和函數(shù)；
Swap(數(shù)據(jù)類型 *a, int i, 數(shù)據(jù)類型 *b, int j)//a[i]與b[j]交換的函數(shù)

int intSumA = 0;
int intSumB = 0;

if ( Sum(a[n]) < Sum(b[n] ) //初始比價兩個數(shù)組的和的大小
{

        
    for(i = 0; i < n; i++)
    {
              intSumA = Sum(a[n]);
        intSumB = Sum(b[n]);
           
        for (j = 0; j < n; j++)
        {
            if ( (intSumA - a[i] + b[j] < intSumB + a[i] - b[j] )
                       && ( a[i] < b[j])
                     )
            {
                Swap(a, i, b, j);
                i = 0;
                break;

            }
            
        }
    }
}
else
{
    //與條件為真時類似處理；
}



pring a[n], b[n];

Bangel

原帖由 ccjjhua 于 2006-11-13 11:42 發(fā)表
把a,b 2數(shù)組的元素放到數(shù)組3（2n大�。� 中進(jìn)行排序，
a 先取最小的，b先取次小的，
然后根據(jù)a,b已取元素和的大小來決定誰來取剩下元素中最小的。策略是，已取得的所有元素之和大的來取C中剩下元素中的最小者。如 ...

這個好像行得通。。。

gnu.linyou

把兩個數(shù)據(jù)放在一起
然后使用 組合 C(n, 2 * n);
把每一個組合得到的值 和   sum / 2 進(jìn)行相減
數(shù)值最小的 組合 當(dāng)作一個數(shù)組， 剩下的當(dāng)作另一個數(shù)組

組合C的 編寫，找現(xiàn)成的排列組合算法，STL里面有一個next_permutation組合算法

iwolcbao

原帖由 mynets 于 2006-11-30 10:40 發(fā)表
If performance is not a key factor, this program's result is very precise. And you can use it to evaluate other algorithms.

[code]
#include <sys/types.h>
#include <unistd.h>
#incl ...

同意這個算法，
貼子是否該有個結(jié)論了。
其實想有個最好的結(jié)果！

tuzhiwei123

先把兩個數(shù)組歸并成一個數(shù)組，再排序，完成后再分割，數(shù)組下標(biāo)為單的為一個數(shù)組，為雙的為另一個數(shù)組，就OK了

dpsuffix

#include <stdio.h>
int c[20];

int mcam(int *a,int *b)
{
        if( *a > *b)
                return 1;
        else if( *a == *b)
                return 0;
        else
                return -1;
}
int printarr(int *a,int size)
{
        int i ;
        for(i = 0;i < size;i++){
                printf("%d,",*a);
                a++;
        }
        printf("\n");
}
int a[] = {10,34,230,400,321,4233,2000,50,320,333};
int b[] = {23,7000,200,634,987,230,640,46,135,257};

int main(int argc,char **argv)
{
        qsort(a,10,sizeof(int),mcam);
        qsort(b,10,sizeof(int),mcam);
        printarr(a,10);
        printarr(b,10);
        int loop = 1;
        int suma,sumb;
        int gap;
        int max,temp;
        int i,j;
        int sub;
        while(loop){
                int chgi=-1,chgj=-1;
                max = 0;
                suma=sum(a,10);
                sumb=sum(b,10);
                gap = (suma-sumb)/2;
                for(i=9;i>=0;i--){
                        for(j=0;j<10;j++){
                                sub = a[i] - b[j];
                                if(gap > 0){
                                        if(max <sub && sub <gap){
                                                max = sub;
                                                chgi = i;
                                                chgj = j;
                                        }
                                }else if(gap < 0){
                                        if( max >sub && sub >gap){
                                                max = sub;
                                                chgi = i;
                                                chgj = j;

                                        }
                                }else{
                                        printf("loop = 0\n");
                                        loop =0;
                                        break;
                                }
                        }
                }
                printf("gap=%d i=%d,j=%d\tmax=%d\n",gap,chgi,chgj,max);

                if(chgi == -1){
                        printf("none change\n");
                        break;
                }
                temp = a[chgi];
                a[chgi] = b[chgj];
                b[chgj]=temp;
                qsort(a,10,sizeof(int),mcam);
                qsort(b,10,sizeof(int),mcam);
                printf("suma=%d,sumb=%d\n",sum(a,10),sum(b,10));
        }
        printf("suma=%d,sumb=%d\n",sum(a,10),sum(b,10));
        printarr(a,10);
        printarr(b,10);
        return 0;
}

int sum(int *a,int size)
{
        int i;
        int sum=0;
        for(i=0;i<size;i++){
                sum+=*a;
                a++;
        }
        return sum;
}

shanan

先把兩個數(shù)組按值排序，再把值順次賦給數(shù)組，就可以滿足題目了

Csky_mxy

我是一只菜鳥，說錯了不要拍俺~~~~~~~~~~多謝。還請各位大俠多支點我錯在了那里！謝謝。

我覺得程序需要有普適性，相信各位高手對這個概念早就熟悉的不能再熟悉了。所以我認(rèn)為求出相對小值也許更加理想，說白了就是n次中我也許很多次取道的值都不是最小的，但是總體上來說，是最小的。

也就是說，可以找到這些數(shù)字處于中間大小的值，然后按照第一大的去a,第二大的去b,第三大的去b,第四大的去a,這樣的一種分配順序來做，我想應(yīng)該可以實現(xiàn)在N次選擇時，可以保障每次所形成的兩個數(shù)組的差在平均的意義上說是最小的。

時間緊迫，在看到題目后1分鐘所反映出的想法，估計有很多不到之處，還請各位大俠高手指點，不要拍磚~~~~~~~~~~~~~~~~~~~~~~~~~~~~俺信心小，膽子薄~~~~~~~~~~~~~

其實，操作系統(tǒng)最大的一個問題就是穩(wěn)定性上，在一種均衡的情況下來得出平均的相對最優(yōu)值，不要執(zhí)著于一次或者某次的最小，而應(yīng)該把眼睛放到N次上，我想這也許是設(shè)計一個大系統(tǒng)的最根本的出發(fā)點吧，在下年級方才24，肯定有不對的地方，還望各大高手前輩多多指教！謝了~~~~~~~~~~~~

Csky_mxy

原帖由 dpsuffix 于 2007-3-7 13:17 發(fā)表
#include <stdio.h>
int c[20];

int mcam(int *a,int *b)
{
        if( *a > *b)
                return 1;
        else if( *a == *b)
                return 0;
        else
         ...

閣下這個程序看著就不舒服！

w18473999

弄個鏈表，然后排序插入
不過挺惡心，華為又是筆試，1、2、3、4面試啥的，nnd完事了才給5K，而且還腆著
臉說我們開始低，不過漲工資是火箭似的， 也好意思說