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

Question

假设您有ksize 的数组N，每个数组都包含从1to 的唯一值N。

你将如何找到平均相距最远的两个数字？

例如，给定数组：

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

那么答案将是 item 1and 2，因为它们在前两个数组中的距离为 2，而在最后一个数组中的距离为 3。

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

我想在 C++ 中实现这样的算法，但对解决方案的任何描述都会有所帮助。

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和 之间的 L1 距离2是|1-3| + |4-2| + |4-1| = 8，这是它们的平均距离（用问题术语来说）乘以k = 3。

话虽这么说，您可以应用近似最近邻算法，使用上面的输入作为数据库，并将数据库中每个点的图像N+1-v作为查询。