Question

2个数组中任意元素的求和问题

比如有一个数组A中有n个元素A1,A2....An,数组B中有m个元素B1,B2...Bm。我想对数组A中的任意元素Ai和数组B中的任意元素Bj求和，并对Ai+Bj的和（共有n*m种不同的组合）进行排序。请问除了遍历以外还有什么效率更好的算法吗

Answer 1

这个问题很有意思！对于加法的话，效率不可能有提升，因为不论如何总是要计算的！

所以现在只看关于排序的算法：如果不去管排序的细致算法的话（这里指冒泡啊，快速算法啊等等），可以作如下分析：

现在可能有两种方法：
1. 对于Ai+Bj的和进行排序，这样，你需要对于n*m个数字进行排序。

2. 将Ai和Bj组成一个数组Cp进行排序。假设从小到大为
A1=1, A2=2, B1=3, A3=4, B2=5, B3=6, B4=7.
那可以肯定的知道A3+B2，A3+B3, A3+B4一定大于A2+B2, A2+B3, A2+B4，所以只需要比较A2+B1是不是大于A3+B2, A3+B3, A3+B4，如果找到比某个大，比某个小，就可以停止比较。以此类推，排序的数量应该远远小于对于Ai+Bj计算完以后n*m个数字进行排序的计算量。

虽然这个问题看似比较简单，但是如果不仔细分析可能不能找到最好的答案，我的那个第二种方法不一定是最完美的，可以再思考一下！

Answer 2

如果可以先把这两个数组排序了，那么可以边求和边确定顺序，省掉了最后的排序工作。

Answer 3

只能遍历。