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

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++ 中实现这样的算法，但对解决方案的任何描述都会有所帮助。

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 下数据库中每个点的图像来应用近似最近邻算法。作为查询。