交换两个序列的元素，使得元素和的差最小化。

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) 的意思是除了序列 1 和 2 本身，我们不需要额外的空间。

有没有什么想法？

另一个相关的问题是：如果我们需要最小化差值的绝对值（最小化 |sum(a) - sum(b)|）呢？

更倾向于用 Python 或 C++ 的思路。

Answer 1

我想到的算法大致是这样的：

1. C = A v B
2. 对C中的#A个元素进行部分排序
3. 从C中前#A个元素的总和中减去后#B个元素的总和。

你要注意的是，并不需要对所有元素进行排序，只需要找到#A个最小的元素就可以了。你给出的例子是：

1. C = {5, 1, 3, 2, 4, 9}
2. C = {1, 2, 3, 5, 4, 9}
3. (1 + 2 + 3) - (5 + 4 + 9) = -12

下面是一个C++的解决方案：

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    // Initialize 'a' and 'b'
    int ai[] = { 5, 1, 3 };
    int bi[] = { 2, 4, 9 };
    std::vector<int> a(ai, ai + 3);
    std::vector<int> b(bi, bi + 3);

    // 'c' = 'a' merged with 'b'
    std::vector<int> c;
    c.insert(c.end(), a.begin(), a.end());
    c.insert(c.end(), b.begin(), b.end());

    // partitially sort #a elements of 'c'
    std::partial_sort(c.begin(), c.begin() + a.size(), c.end());

    // build the difference
    int result = 0;
    for (auto cit = c.begin(); cit != c.end(); ++cit)
        result += (cit < c.begin() + a.size()) ? (*cit) : -(*cit);

    // print result (and it's -12)
    std::cout << result << std::endl;
}

Answer 2

修订后的解决方案：

1. 把两个列表合并成一个，记作 x = merge(a,b)。

2. 计算这个合并后列表 x 的中位数（复杂度是 O(n)，详细信息可以查看 这里）。

3. 根据这个中位数，在列表 a 和 b 之间交换元素。也就是说，找一个在 a 中小于中位数的元素，找一个在 b 中大于中位数的元素，然后把它们交换。

最终的复杂度是：O(n)

最小化绝对差值是 NP 完全问题，因为它和背包问题是等价的。