多个数组中两个数字间的最大平均距离

Question

假设你有k个大小为N的数组，每个数组都包含从1到N的唯一值。如何找出平均距离最远的两个数字？

例如，给定以下数组：

[1,4,2,3]
[4,2,3,1]
[2,3,4,1]

那么答案将是项目 1 和 2，因为它们在前两个数组中的距离相差 2，在最后一个数组中相差 3 个数字。

我知道一种 O(kN^2) 的解决方案（通过测量每对数字在 k 个数组中的距离），但是否有更好的解决方案？

我想在 C++ 中实现这样的算法，但任何解决方案说明都将非常有帮助。

- Magnus E-F

Answer 1

经过线性时间转换后，该问题归结为使用L1距离计算一组点的直径。遗憾的是，这个问题受到维数灾难的影响。

给定：

    1 2 3 4
1: [1,4,2,3]
2: [4,2,3,1]
3: [2,3,4,1]

我们计算

    1 2 3
1: [1,4,4]
2: [3,2,1]
3: [4,3,2]
4: [2,1,3]

然后 1 和 2 之间的L1距离为 |1-3| + |4-2| + |4-1| = 8，这是它们平均距离（在问题术语中）乘以 k = 3。

话虽如此，您可以使用上述输入作为数据库，并使用每个点在 N+1-v 下的图像作为查询来应用近似最近邻算法。

- David Eisenstat

---

这个参考资料提出了一种随机算法，其期望线性运行时间可能会引起OP的兴趣。 - hilberts_drinking_problem

@hilberts_drinking_problem 可能有用，但只适用于低维度。 - David Eisenstat

你觉得能否将这个方法与另一个答案中描述的启发式方法结合起来？ - Magnus E-F

@MagnusE-F，有很多近似最近邻算法可供选择。我修改了我的答案，以便将此问题简化为ANN。 - David Eisenstat

Answer 2

我有一个关于最佳情况的建议。您可以采用启发式方法。

例如，如果N = 4，则N-1 = 3将是最大距离，1将是最小距离。平均距离为10/6 = 1.66667（数组中对数之间的距离总和/数组中对数的数量）。

然后，您知道如果两个数字在k/2个数组的边缘上（大多数情况下），即使它们在其他k/2个数组中只相隔1个距离，它们也已经在平均值之上（>= 2）。这可能是O(2k) = O(k)的最佳情况解决方案。

- samthegolden

---

这似乎是一个不错的方法。在我的情况下，N比k大得多，我认为启发式算法会表现得很好。 - Magnus E-F

这个算法的最坏情况怎么样？它仍然是O(k N^2)吗？ - Jérôme Richard

@JérômeRichard 我们没有改变算法，我们只是添加了一种启发式方法，如果适用的话，仅适用于良好的情况。在最坏的情况下，主要算法也能解决它。 - samthegolden