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

norlan

/*
解法假设：

1、假设存在数组a[n],b[n],且Sum(a[n]) < Sum(b[n]);

2、假设在数组a[n]与b[n]中，不存在元素a[i],使Sum(a[n]) < Sum(b[n])，且Sum(a[n])的值比上次求和的值大，则数组Sum(a[n])与数组Sum(b[n])
的差值最小。



*/


算法：

Sum(数据类型 *p, int n)//数组n的求和函数；
Swap(数据类型 *a, int i, 数据类型 *b, int j)//a[i]与b[j]交换的函数

int intSumA = 0;
int intSumB = 0;

if ( Sum(a[n]) < Sum(b[n] ) //初始比价两个数组的和的大小
{

        
    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 发表
把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最小的，b先取次小的，
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。策略是，已取得的所有元素之和大的来取C中剩下元素中的最小者。如 ...

这个好像行得通。。。

gnu.linyou

把两个数据放在一起
然后使用 组合 C(n, 2 * n);
把每一个组合得到的值 和   sum / 2 进行相减
数值最小的 组合 当作一个数组， 剩下的当作另一个数组

组合C的 编写，找现成的排列组合算法，STL里面有一个next_permutation组合算法

iwolcbao

原帖由 mynets 于 2006-11-30 10:40 发表
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 ...

同意这个算法，
贴子是否该有个结论了。
其实想有个最好的结果！

tuzhiwei123

先把两个数组归并成一个数组，再排序，完成后再分割，数组下标为单的为一个数组，为双的为另一个数组，就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

先把两个数组按值排序，再把值顺次赋给数组，就可以满足题目了

Csky_mxy

我是一只菜鸟，说错了不要拍俺~~~~~~~~~~多谢。还请各位大侠多支点我错在了那里！谢谢。

我觉得程序需要有普适性，相信各位高手对这个概念早就熟悉的不能再熟悉了。所以我认为求出相对小值也许更加理想，说白了就是n次中我也许很多次取道的值都不是最小的，但是总体上来说，是最小的。

也就是说，可以找到这些数字处于中间大小的值，然后按照第一大的去a,第二大的去b,第三大的去b,第四大的去a,这样的一种分配顺序来做，我想应该可以实现在N次选择时，可以保障每次所形成的两个数组的差在平均的意义上说是最小的。

时间紧迫，在看到题目后1分钟所反映出的想法，估计有很多不到之处，还请各位大侠高手指点，不要拍砖~~~~~~~~~~~~~~~~~~~~~~~~~~~~俺信心小，胆子薄~~~~~~~~~~~~~

其实，操作系统最大的一个问题就是稳定性上，在一种均衡的情况下来得出平均的相对最优值，不要执着于一次或者某次的最小，而应该把眼睛放到N次上，我想这也许是设计一个大系统的最根本的出发点吧，在下年级方才24，肯定有不对的地方，还望各大高手前辈多多指教！谢了~~~~~~~~~~~~

Csky_mxy

原帖由 dpsuffix 于 2007-3-7 13:17 发表
#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，而且还腆着
脸说我们开始低，不过涨工资是火箭似的， 也好意思说