假设您有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 ++实现这样的算法，但是对解决方案的任何描述都会有所帮助。
我有个建议最好的情况。您可以遵循启发式方法。
例如，您知道如果N=4，则N-1=3将是最大距离，而1将是最小距离。平均距离为10/6=1,66667（阵列中的线对之间的距离之和/阵列中的线对数目）。
然后，您知道，如果k/2数组的边上有两个数字（大多数情况下），即使它们只是[[ C0]在其他2数组中的距离。对于1 = k/2的最佳情况，这可能是一个解决方案。
这里有一个怪异的想法：将每个数字的点描述为“曼哈顿”线段的集合。在一定程度上，我们可以有公式来找到这些定义的线段之间的区域，因此交叉的次数越少，我们可以将每对计算分组（假设每个数字在每个数组中出现一次）。
经过线性时间变换为数字编制索引之后，这个问题归结为计算相对于L1距离的一组点的直径。不幸的是，这个问题受到维度的诅咒。