求解一道面试题

zheyitian

我看过这道题已经很多次了，也许看过答案了，但此时看到也往了如何解答，如题：

有A、B两个数组，其大小一样，如
A[n]={23，5，98，57，9，99}；
B[n]={45，21，78，55，97，32}；
现在可以交换A、B中的元素，使得A、B之间的差异最小。

主要是问算法，解题思路。
（注：本想发起悬赏的，但资金真的是不足啊~~~）

sidfate

差异最小值是值sum(A[i]-B[i])，i从0-5的累加最小吗？

sidfate

如何如楼上所说，那么此题思路与下题相同：
给定2个元素相同的字符窜，如str1=“abcde”，str2=“bcdae”，求str1要移动几步编程str2（一次只能移动相邻的两个字符）

你先想下上题的思路是怎么样的，想通了就应该懂了，如果不明白我还有上题的源代码

kaizhiyu

麻烦一点！！就是进行双层循环！！！

zheyitian

sidfate 发表于 2014-3-11 18:35

                               
登录/注册后可看大图

差异最小值是值sum(A-B)，i从0-5的累加最小吗？

对，差异最小就是这样。
比如说
A={1,2,3}
B={4,5,6}
那么结果是
A={1，4，6}
B={2，3，5}
是一种答案，它们相差为1.

zheyitian

kaizhiyu 发表于 2014-3-11 19:07

                               
登录/注册后可看大图

麻烦一点！！就是进行双层循环！！！

说一下思路，如何双层循环？

sidfate

按你这么说不就是把两个数组的所有数（2N个）放一起排个序，然后第i个数放到数组A，第i+1个·数放到数组B中（i从0-N-1）

zheyitian

sidfate 发表于 2014-3-11 20:00

                               
登录/注册后可看大图

按你这么说不就是把两个数组的所有数（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不一定必须要分开的

sidfate

如果按我的方法
A={1,2,4}
B={3,5,10}
就可以转化为：
A={1,3,5}
B={2,4,10}
这个答案不对吗？

zheyitian

sidfate 发表于 2014-3-11 20:25

                               
登录/注册后可看大图

如果按我的方法
A={1,2,4}
B={3,5,10}

你看他们差异：
sum（A）=9
sum（B）=16

它的答案应该是
A={1,2,10}
B={3,4,5}

sidfate

好吧，我理解错题意了，我以为是对应每一位之差累加的最小值，我再想想

sidfate

思路：
      设两数组所有数（2N个）总和为SUM，要是两数组差值最小（最小为0），最小为0是说明单数组之和为SUM/2，但是很多情况是不等于的，所以我们的目的从2N个数中选出N个数之和最接近于SUM/2。

      如果N数量较小，用枚举法比较容易实现，枚举出的个数可以用排列组合来求，但是N如果很大，枚举法就效率太低，暂时还没有N很大的时候后的思路=  =。

zheyitian

sidfate 发表于 2014-3-11 21:31

                               
登录/注册后可看大图

思路：
      设两数组所有数（2N个）总和为SUM，要是两数组差值最小（最小为0），最小为0是说明单数组之和 ...

很好啊。。。网上也有一种方法：
http://blog.sina.com.cn/s/blog_73b8a3f00100wmut.html

你的思路能自己编出来么，这是一个不错的题。

sidfate

zheyitian 发表于 2014-3-11 21:38

                               
登录/注册后可看大图

很好啊。。。网上也有一种方法：
http://blog.sina.com.cn/s/blog_73b8a3f00100wmut.html

我明天写出来我们交流交流！

ghort_rider

之前比赛时有考到这个题，但是没做出来{:7_163:}