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

youzj326

1、a b各自从小到大排序
2、分别计算出a和b的数组元素和max_a和max_b
3、计算出两数组元素和的最大值之差d，如果max_a > max_b,则d = max_a - max_b;
4、调函数fix(a, b)进行处理，函数第一个参数为较大的那个数组，第二个参数为较大的那个数组，主要逻辑处理为两重循环：
   for (i = n; i >= 0; i--)
   {
      for (j = 0; j < n; j++)
      {
         tmp = (max_a - a[i] + b[j]) - (max_b + a[i] -  b[j]);
         if (tmp > 0 && tmp < v)
         {
             v = tmp; // 的初始值为d
             pos_a = i;//保存a要交换的元素位置
             pos_b = j;//保存b要交换的元素位置
         }
      }
   }

饮马黄河源

所有数都存入一个临时数组，排序后在交叉取数

caochao9008

/* ************************************************************************
*       Filename:  test.c
*    Description:  
*        Version:  1.0
*        Created:  2012/3/29? *       Revision:  none
*       Compiler:  gcc
*         Author:  曹超
*        Company:  实现两个任意数组的差值最小化的转换
* ************************************************************************/
#include <stdio.h>

static int change(int *a,int *b,int n)
{
        int i = 0;
        int j = 0;
        int k=0;
        int m = 0;
        int mm=0;
        int mmm=0;
        int flag=0;
        int cout=0;
        int num=0,min=0,max=0,other=0;
        int temp[200];
        int *aa,*bb;
        int *p ;
        aa=a;
        bb=b;
        for(i=0;i<n;i++)
        {
                temp[i]=*aa++;
                max = max+temp[i];
        }
        for(i=n;i<(2*n);i++)
        {
                temp[i]=*bb++;
        max = max+temp[i];
        }
        p=temp;
        min = max;
        for(i=0;i<n+1;i++)
                for(j=i+n-1;j<(2*n);j++)
                {
                        num = 0;
                        for(k=0;k<n-1;k++)
                        {
               num=*(p+k+i)+num;
                       //printf("temp[%d]+",k+i);
                        }
                        num=*(p+j)+num;
                        //printf("temp[%d]=%d\n",j,num);
                        cout++;
                other = max - num;
                        if(other>=num)
                        {
                                other = other-num;
                        }
                        else
                        {
                                other = num - other;
                        }
                        if(other<min)
                        {
                                min = other;
                                for(m=0;m<n-1;m++)
                                {
                                   a[m]= *(p+m+i);
                                }
                                    a[m] = *(p+j);
                                //for(m=0;m<(n);m++)
                //{
                                        //printf("%d,",a[m]);
                                //}       
                                //printf("\nmin=%d\n",min);
                                mmm=0;
                                bb=b;
                    for(mm=0;mm<(2*n);mm++)
                                        {
                                            for(m=0;m<n-1;m++)
                                                {
                                                        if((m+i)==mm)                                               
                                                        {
                                                                flag=1;
                                                                break;
                                                        }
                                                }
                                                if(flag==0&&(mm!=j))
                                                {
                                                        *(bb+mmm)=temp[mm];
                                                         mmm++;
                                                }
                                                flag=0;
                                        }
                                //        for(m=0;m<(n);m++)
                //{
                                //        printf("%d,",b[m]);
                                //}
                                //        printf("\n");
                        }
                }
                printf("计算次数：%d\n最小差值：%d\n",cout,min);
               
                return 0;
}
int main()
{
        int a[3]={0,0,1};
        int b[3]={2,3,999};
        int n=0;
        change(a,b,3);
        printf("结果\n a=");
        for(n=0;n<3;n++)
        {
                printf("[%d] ",a[n]);
        }
        printf("\n b=");
        for(n=0;n<3;n++)
        {
                printf("[%d] ",b[n]);
        }
        printf("\n");
}

enough_zerg

caochao9008 发表于 2012-03-29 11:43
/* ************************************************************************
*       Filename:  tes ...

这代码烂的。。。

caochao9008

刚写完就发了上来，因为用的TAB缩进，复制过来就乱了。

_Rayx

这个问题是NPC的，随机调整吧。

davidfoxhu

数组a所有元素和sum_a
数组b所有元素和sum_b
如果sum_a==sum_b
      return;
对数组a的所有元素遍历for(i=0;i<n;i++)
      对数组b的所有元素for(j=0;j<n;j++)
            temp_a=sum_a-a+b[j];
            temp_b=sum_b+a-b[j];
            如果temp_a==temp_b
                  交换a和b[j]
                   return;
       如果temp_a>temp_b
                  如果sum_a〉sum_b
                        如果(sum_a-sum_b)>(temp_a-temp_b)
                              交换a和b[j]
                              sum_a=temp_a
                              sum_b=temp_b
                              continue;
                  else
                         如果(sum_b-sum_a)>(temp_a-temp_b)
                               交换a和b[j]
                               sum_a=temp_a
                               sum_b=temp_b
                               continue;
            else
                   跟上面几乎一样的处理

qingjoin

先把两个数组里的值取出来，然后存到别一个数组里。再把这个数组里的元素排序，然后交叉分别放到第一个，和第二个数组里。
我是这么想的。不知道还有没有更好的想法！

yrhsilence

这题简单的地方就在于分配好后两个数组中数的个数是还是相同的。所以很简单的，先把a，b数组合并为一个c数组，由大到小排序，然后开始从c中取数，往数组a1和b1中添加。添加规则是添加进去后两数组和sum_a1和sum_a2的差值最小。如果sum_a1和sum_a2相同，那就往现在数组中数的个数小的那个数组中添加。最后一个数组如果满了，就把剩下的全部塞到另一个数组中！

实际上比较难的是这样的，一串数字，把它分为两个数组a和b，其中sum(a)和sum(b)的差值最少。这个a和b数组中数的个数是不保证相等的，就比较难了，要用动态规划做，忘了该怎么做了！

xfunl

一直用最小的减去最大的，全是负数，这算最小了不？