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

416679828

我感觉没大家说的那么复杂吧！
因为a,b数组可以交换数据，而且数组长度相等，那么就有：
1：输入a,b数组后把他们放到一个临时数组c里面，对c进行递增排序
2：然后取c最大和最小的放到a里面，然后取次最大和次最小的放到b里面
3：循环第二步即可
下面是我的代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include<stdbool.h>
int comp1(const void *a,const void *b){
return(*(int *)a-*(int *)b);
}
int main()
{
    int n,i,j,t=0,y1=-1,y2=-1,suma=0,sumb=0;
    bool flag=true;
    printf("输入N的大小:");
    scanf("%d",&n);
    int* a=malloc(n*sizeof(int));
    int* b=malloc(n*sizeof(int));
    int* c=malloc(2*n*sizeof(int));
    printf("输入数组a:");
    for(i=0;i<n;i++){
    scanf("%d",a+i);
    c[t++]=a[i];
    }
     printf("输入数组b:");
    for( i=0;i<n;i++){
    scanf("%d",&b[i]);
    c[t++]=b[i];
    }
    t--;
    qsort(c,2*n,sizeof(int),comp1);
    if(n%2==0){
    for( i=0;i<n;i++){
        if(flag){
        a[++y1]=c[i];suma+=a[y1];
        a[++y1]=c[2*n-1-i];suma+=a[y1];
        flag=false;
        }
        else{
            b[++y2]=c[i];sumb+=b[y2];
        b[++y2]=c[2*n-1-i];sumb+=b[y2];
        flag=true;
        }
    }
    }
    else{
        for( i=0;i<n-1;i++){
        if(flag){
        a[++y1]=c[i];suma+=a[y1];
        a[++y1]=c[2*n-1-i];suma+=a[y1];
        flag=false;
        }
        else{
            b[++y2]=c[i];sumb+=b[y2];
        b[++y2]=c[2*n-1-i];sumb+=b[y2];
        flag=true;
        }
    }
    if(suma<=sumb){
    a[++y1]=c[n];suma+=a[y1];
    b[++y2]=c[n-1];sumb+=b[y2];
    }
    else{
        a[++y1]=c[n-1];suma+=a[y1];
    b[++y2]=c[n];sumb+=b[y2];
    }
    }
    printf("数组c:");
    for(i=0;i<2*n;i++)
    printf("%d ",c[i]);
    printf("\n");
    printf("数组a:");
    for(i=0;i<n;i++)
    printf("%d ",a[i]);
    printf("\n");
    printf("数组b:");
    for(i=0;i<n;i++)
    printf("%d ",b[i]);
    printf("\n");
    printf("数组a的和:");
    printf("%d\n",suma);
    printf("数组b的和:");
    printf("%d\n",sumb);
    printf("数组a和b的最小差为:");
    printf("%d\n",abs(suma-sumb));

return 0;
}
不知道对不对，反正我的思路是这样,因为他们能互相交换，总能取得这样的解

zhaowanqi

大概思路：先把两个数组从小到大排序，然后分别求元素和，
假设数组a元素和较大，用其最小的数，到另外一个数组中找到比这个数大，但差最少的数交换，并记录元素和之差

注意：上面的交换保证了交换时值的变化是最小的，这样才能保证和之差最小，和之差大于0和小于0是临界点

只要a的元素和大于b的，就一直循环到B元素和比a的大
当B元素和比a的大，比较和上一次交换保存下来的和之差，谁最小，就以哪一次的交换为最终结果

解法如下：
一：分别对两个数组进行排序，从小到大,如：
int[] a={......};
int[] b={......};
sort(a);
sort(b);
int c,d;//两个数组中元素分别的和
e,f;    //c , d 的差，差大于0时E,小于0时F


二：循环以下步骤
1：对两个数组中的元素进行分别相加

for(int i=0;i<n;i++)
{
     c+=a[i];
    d+=b[i];
}
2:比较c,d的大小，并把值保存 e=c-d （这里假设c比d大，其他情况请自己去完善）
2：用a的最小数，和b当中所有元素进行比较，找到比a最小数大且差最小的数，然后交换二者的位置
swap(a[0],b[n]);
3：对两个数组重新进行从小到大的排序
sort(a);
sort(b);
4:再次比较c,d的差，如果大于0，继续循环

三，如果小于0，终止循环，并把差保存到f=d-c,比较e,f的值，如果f大于e,把最后一次交换回退

zhaowanqi

比较完整一点的思路（借鉴了前面那些CUer的想法）

一：用一个临时数组来保存a和b的元素，排序后再依次放入a,b:
取c最大和最小的放到a里面，然后取次最大和次最小的放到b里面

二：参见372楼，

如果没有一，那么有可能出现a中的所有数都比b中的数大，无法交换
先取得大体上的平衡，再来微调

caseboy01

好吧，我给大家公布正确答案。数组A 和 B (ARRAY A B)
最终的结果怎么描述： 替换任意俩个数组的数字(swap(a[i], b[j]))，会使得俩个数组的和差 ( |sum(A) - sum(B)| )变大(这里的变大是相对于交换元素前和交换元素后的 )。
那只要循环执行： 替换俩个数组的元素，如果 数组的和差变小，则替换，如果数组的和差变大，则不替换
循环执行上面的过程，直到没有元素可以替换为止，如此得到的一定是标准答案。

syzcch

很简单的问题 不保证最优贪心 保证最优动态规划

ddzt10086

拿回去思考

cygamelife

排序，交叉取数

Sevk

很多场合不需要最准确的解，但需要最高速的解。比如Qos

a8645217

A、B一起放入C[2n]中由大到小排序
准备a、b两个栈
对C进行遍历
循环{
若a栈和小于等于b栈和
C[i]压进a栈
否则进b栈
}直到a、b中任意一栈的元素数量达到n，退出循环
C中余下数据全部压入数量未满n的栈

初面很普通的题，很特别？

weiyage

题目说用交换数组的方式
1.将数组替换：a[i]<=b[i] && a[i+1]>b[i]
2.将a[i]与b[i]做减法，并且将值记录到c[i]
3将c[i]进行排序，并且将a[i]和b[i]的值进行对换
4.将得出c[i]没隔1，取负数，求和，
5.将最小的结果中，取负1进行交换