求解一道面试题
我看过这道题已经很多次了，也许看过答案了，但此时看到也往了如何解答，如题：有A、B两个数组，其大小一样，如
A={23，5，98，57，9，99}；
B={45，21，78，55，97，32}；
现在可以交换A、B中的元素，使得A、B之间的差异最小。
主要是问算法，解题思路。
（注：本想发起悬赏的，但资金真的是不足啊~~~）
差异最小值是值sum(A-B)，i从0-5的累加最小吗？ 本帖最后由 sidfate 于 2014-3-11 18:56 编辑
如何如楼上所说，那么此题思路与下题相同：
给定2个元素相同的字符窜，如str1=“abcde”，str2=“bcdae”，求str1要移动几步编程str2（一次只能移动相邻的两个字符）
你先想下上题的思路是怎么样的，想通了就应该懂了，如果不明白我还有上题的源代码 麻烦一点！！就是进行双层循环！！！ sidfate 发表于 2014-3-11 18:35 static/image/common/back.gif
差异最小值是值sum(A-B)，i从0-5的累加最小吗？
对，差异最小就是这样。
比如说
A={1,2,3}
B={4,5,6}
那么结果是
A={1，4，6}
B={2，3，5}
是一种答案，它们相差为1. kaizhiyu 发表于 2014-3-11 19:07 static/image/common/back.gif
麻烦一点！！就是进行双层循环！！！
说一下思路，如何双层循环？ 按你这么说不就是把两个数组的所有数（2N个）放一起排个序，然后第i个数放到数组A，第i+1个·数放到数组B中（i从0-N-1） sidfate 发表于 2014-3-11 20:00 static/image/common/back.gif
按你这么说不就是把两个数组的所有数（2N个）放一起排个序，然后第i个数放到数组A，第i+1个·数放到数组B中 ...
按你说的，那N+1这个位置上的数没有了？我想你的意思可能是排序后一个放A下一个放B，依次下去，如下面的结果：
A={1,3,5}
B={2,4,6}
但是结果也可能是：
A={1，4，5}
B={2，3，6}
再说我举的那个例子太特殊了，如果是
A={1,2,4}
B={3,5,10}
呢？
i和i+1不一定必须要分开的 如果按我的方法
A={1,2,4}
B={3,5,10}
就可以转化为：
A={1,3,5}
B={2,4,10}
这个答案不对吗？ sidfate 发表于 2014-3-11 20:25 static/image/common/back.gif
如果按我的方法
A={1,2,4}
B={3,5,10}
你看他们差异：
sum（A）=9
sum（B）=16
它的答案应该是
A={1,2,10}
B={3,4,5} 好吧，我理解错题意了，我以为是对应每一位之差累加的最小值，我再想想 思路：
设两数组所有数（2N个）总和为SUM，要是两数组差值最小（最小为0），最小为0是说明单数组之和为SUM/2，但是很多情况是不等于的，所以我们的目的从2N个数中选出N个数之和最接近于SUM/2。
如果N数量较小，用枚举法比较容易实现，枚举出的个数可以用排列组合来求，但是N如果很大，枚举法就效率太低，暂时还没有N很大的时候后的思路==。 sidfate 发表于 2014-3-11 21:31 static/image/common/back.gif
思路：
设两数组所有数（2N个）总和为SUM，要是两数组差值最小（最小为0），最小为0是说明单数组之和 ...
很好啊。。。网上也有一种方法：
http://blog.sina.com.cn/s/blog_73b8a3f00100wmut.html
你的思路能自己编出来么，这是一个不错的题。 zheyitian 发表于 2014-3-11 21:38 static/image/common/back.gif
很好啊。。。网上也有一种方法：
http://blog.sina.com.cn/s/blog_73b8a3f00100wmut.html
我明天写出来我们交流交流！ 之前比赛时有考到这个题，但是没做出来{:7_163:}
页:
[1]