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

anthony1983

  IBM的老题，人家是天平称砝码，这里弄个数组。。。。。。
而且8分钟写代码太难了，写伪码还差不多，如果之前没见过类似的题话。

RobinHoo

我的想法是，求出所有数的和平均值，然后从大的数组里取一数大于平均值且最近的与另一组里的里小于平均数且最近的交换，如此循环，直到两数组之间的差不变为止。

[ 本帖最后由 RobinHoo 于 2007-11-23 17:49 编辑 ]

anthony1983

想得太复杂了吧，根本不用排序，因为排序只会多一道操作而已，时间复杂度，还是N的平方， 把两个数组之差算出来，然后两两比较就可以了！

include <stdio.h> #define MAX_LEN 10 int main() {         int a[MAX_LEN];         int b[MAX_LEN];         int i, asum=0, bsum=0;         for (i=0; i<MAX_LEN; i++) {                 a[i] = rand();                 asum+=a[i];                 b[i] = rand();                 bsum+=b[i];         }         for (i=0; i<MAX_LEN; i++)                 printf("%d ", a[i]);         printf("\n");         for (i=0; i<MAX_LEN; i++)                 printf("%d ", b[i]);         printf("\n");         int d = asum - bsum;         printf("== %d \n", d);         if (d == 0)                 goto over;         int j, d0, asum0, bsum0, temp;         for (j=0; j<MAX_LEN; j++)                 for (i=0; i< MAX_LEN; i++) {                         asum0 = asum - a[i] + b[j];                         bsum0 = bsum - b[j] + a[i];                         d0 = asum0 - bsum0;                         if (abs(d0) < abs(d)) {                                 temp = a[i];                                 a[i] = b[j];                                 b[j] = temp;                                 asum = asum0;                                 bsum = bsum0;                                 d = d0;                                 if (d == 0)                                         goto over;                         }                 } over:         asum = 0;         for (i=0; i<MAX_LEN; i++) {                 asum+=a[i];                 printf("%d ", a[i]);         }         printf("\n %d\n", asum);         bsum =0;         for (i=0; i<MAX_LEN; i++) {                 bsum+=b[i];                 printf("%d ", b[i]);         }         printf("\n %d\n", bsum);         printf("===== %d\n", d); }

[ 本帖最后由 anthony1983 于 2007-11-23 20:30 编辑 ]

anthony1983

原帖由 simohayha 于 2007-11-23 19:16 发表
把两个数组合并然后排序，然后再交叉放较大的元素..

0 ， 0， 2， 2， 3 ， 10

怎么放？

anthony1983

有人挖尸体，这都是一年前的帖子了，别顶了，多傻的题目啊 ，此题的解法和数组大小N有关

shmilylxx

原帖由 shmilylxx 于 2007-11-23 15:16 发表
思考半个小时，
有了个思路，稍微整理一下，
存在 A【N】,B【N】

取这两个数组并，按照大小排序，比如成为 C【N*2】
再从大到小，两两相减D【i】=C【2I】-C【2i+1】
将D【N】按照绝对值排序，
先将C【0 ...

再检查了一下，我的算法还是有问题，
振荡收敛，但是没不要将振荡放那么大......

另外，前面回复有人给出了效率不错的答案，不再重复了~

nuclearxin

流氓类似机器算法
所有元素和/2=x
所有组合 取一半的和与x比较 留下小的
瞎说不懂呵呵

holton

将a,b所有元素按降序排序后放到数组c中，然后将a,b所有元素设为0。sum_a,sum_b分别表示数组a,b当前元素和。从c取出来的元素放到sum_x小的数组中去，如果sum_a == sum_b则放到元素个数多的数组里，如果a,b元素个数一样就可以随便放。直到任何一个数组元素个数到达n，就将剩下的数全放到另外一个数组上。
前面已经有人提出来了，我的想法差不多。直觉觉得这样是可以的，但是不知道怎么证明。

文化机器人

同意9楼的，枚举吧