交换两个序列的元素,使元素和的差异变得最小.

Question

面试问题:

给定两个非有序整数序列a和b,其大小为n时,所有的数字是随机选取的:交换的元素a和b,使得所述元素的总和a减去的元素的总和b是最小的.

举个例子:

a = [ 5 1 3 ]
b = [ 2 4 9 ]

结果是(1 + 2 + 3) - (4 + 5 + 9)= -12.

我的算法:将它们排序在一起,然后将第一个最小的n整数放入a和放入b.它的时间为O(n lg n),空间为O(n).我不知道如何将其改进为时间为O(n)且空间为O(1)的算法.O(1)意味着除了seq 1和2之外我们不需要更多的额外空间.

有任何想法吗 ？

另一个问题是:如果我们需要最小化差异的绝对值(最小化|sum(a) - sum(b)|)怎么办？

首选python或C++思想.

Answer 1

修订后的解决方案

1. 合并两个列表x = merge(a,b).

2. 计算x的中位数(复杂度O(n)见http://en.wikipedia.org/wiki/Selection_algorithm)

3. 在a和b之间使用这个中间交换元素.也就是说,找到一个小于中位数的元素,在b中找到一个大于中位数的元素并交换它们

最终复杂性:O(n)

最小化绝对差值是NP完全的,因为它等同于背包问题.