liqiankun 发表于 2007-1-24 12:46:29

一个算法问题，同志们看看

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

cdj0823 发表于 2007-1-24 16:23:40

把a,b 2数组的元素放到数组3（2n大小） 中进行排序， a 先取最小的，b取次小的， 然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。
策略是，已取得的所有元素之和大的来取C中剩下元素中的最小者。如此反复，直到取完。每次都是a,b各取一个。sdlkfj2

JamesGosling 发表于 2007-1-25 22:18:55

是一道华为的面试题
for(var i = 0;i<10;i++){
if(sum(B)<sun(A){ //如果B的和小于A的和则把A最大元素给B
   B = Max(A) // 把A里最大的元素给B
   A.SPLITE(MAX(A))//把这个元素删除
}else{
   B = MIN(A)//如果B的和大于了A的和则把A最小的元素给B
   A.SPLITE(MIN(A))
}
}

linkalee 发表于 2007-1-26 23:33:05

原帖由 JamesGosling 于 2007-1-25 22:18 发表
是一道华为的面试题
for(var i = 0;i<10;i++){
if(sum(B)<sun(A){ //如果B的和小于A的和则把A最大元素给B
   B = Max(A) // 把A里最大的元素给B
   A.SPLITE(MAX(A))//把这个元素删除
}else ...

能否请教一下把A中的最大的元素给B，然后删除A中的元素，那B中的元素如何处理?直接被覆盖吗？？

tunglee 发表于 2007-1-27 09:07:18

linkalee，是的，就是覆盖了
关键是从A中把这个元素删除了，A数组中没有给赋值，
好像只是写了一个程序的伪码吧！

linkalee 发表于 2007-1-27 16:53:55

原帖由 tunglee 于 2007-1-27 09:07 发表
linkalee，是的，就是覆盖了
关键是从A中把这个元素删除了，A数组中没有给赋值，
好像只是写了一个程序的伪码吧！
不太明白，题目要求是A和B的元素互换啊。能否说清楚一些啊。
页: [1]
查看完整版本: 一个算法问题，同志们看看