n年前传说中华为面试题(8分钟写出代码)

有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小

 

思路：

用二重循环把a中的每个元素和b中的每个元素逐个“尝试交换”，
如果是差值变小就维持交换，否则就交换回去，也就是不交换，
每有一次交换，“尝试交换”的二重循环就重新从头开始，
直到没有任何交换使差值变小为止。
这种方法不是很简洁，但的确是可行的。
前边贴出代码的算法，有过一次交换后，循环没有从头开始，所以是错误的。例如a[1]和b[j]交换后，b中的元素改变了，不能再保证a[0]和b[ i ]交换不会使差值变小，这时循环必须从头开始。

 

实现代码：

#include <stdio.h>
#include <math.h>

#define N 10

void ary_init(int a[], int b[]){ //初始化数组
    int i;
    for (i=0; i<N; i++){
        a[i] = rand()%10000;
    }
    for (i=0; i<N; i++){
        b[i] = rand()%100;
    }
    return;
}
long sum(int a[]){ //数组求和
    int i;
    int s;
    for (s=0,i=0; i<N; i++){
        s += a[i];
    }
    return s;
}

void change(int *a, int *b){ //数组元素交换
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

void prt_ary(int a[], int b[]){ //列印两数组元素及各自元素和
    int i;
    for(i=0; i<N; i++){
        printf("%5d ", a[i]);
    }
    printf("\n");
    for(i=0; i<N; i++){
        printf("%5d ", b[i]);
    }
    printf("\n");
    printf("%d\n", sum(a));
    printf("%d\n", sum(b));
}
int slove(int a[], int b[]){
    int i;
    int j;
    int is_swap = 0;//是否修交换过数据标志
    int ab_diff;

    ab_diff = abs(sum(a)-sum(b));
    for (i=0; i<N; i++){
        for (j=0; j<N; j++){
            change(a+i, b+j);
            if (abs(sum(a)-sum(b)) < ab_diff){//判断是否需要交换元素
                is_swap = 1; //置位交换标志
                ab_diff = abs(sum(a)-sum(b)); //更新差值
            }
            else{
                change(b+j, a+i);//不交换

            }
        }
    }
    return is_swap;
}
int main(){

    int a[N];
    int b[N];

    ary_init(a,b);//数组元素初始化
    prt_ary(a, b);//列印当前数组状态
    while (slove(a, b));//处理数组
    prt_ary(a, b);//列印交换后数组状态
    getch();
}

本文根据cu精华贴整理而来，在此对代码贡献者表示感谢：