华为面试题

只看该作者 · 2012-5-12 09:33

有两个序列a,b，大小都有n，序列元素的值任意整数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b无素的和]之间的差最小。
例如：
var a = [100, 99, 98, 1, 2, 3];
var b = [1, 2, 3, 4, 5, 40];

只看该作者 · 2012-5-12 09:55

给个思路：
1、两数组A和B归并为一个排好序的数组C
2、清空A和B
3、从C中每次取两个元素分别放入A和B

取数原则：
1、取第一个和最后一个放入A
2、取第二个和倒数第二个放入B
3、依此类推
4、若取到最后只剩两个数了，计算A的和与B的和，将大的放入‘和’较小的数组，小的放入‘和’较大的数组

只看该作者 · 2012-5-12 09:58

先将两个数组快排得到：
1，2，3，98，99，100
1，2，3，4，5，40
然后归并成一个数组c:
1, 1, 2, 2, 3, 3, 4, 5, 40, 98, 99, 100
然后从c中按顺序取值分别给数组a和b，同时注意，如果上次a分到了一个较大的数，那么下次就给它分配一个小一点的数，反之亦然。