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

原文 标签 arrays algorithm performance

假设您有 k大小数组 N ,每个都包含来自 1 的唯一值至 N .

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

例如,给定数组:

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

那么答案将是项目 12 ,因为它们在前两个数组中的距离为 2,而在最后一个数组中的距离为 3。

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

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

最佳答案

在对数字进行索引的线性时间变换之后,这个问题归结为计算一组点相对于 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 下数据库中每个点的图像来应用近似最近邻算法。作为查询。

关于arrays - 跨多个数组的两个数字之间的最大平均距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60546096/

相关文章:

android - 带有字符串参数的Android中的shamsi/Jalali日历

algorithm - 遗传算法时间表编码?

java - 使用斯坦福 CoreNLP 进行惰性解析以仅获取特定句子的情绪

android - 我的Android应用首次打开时需要很长时间才能加载

java - 测试对象是否为空的有效方法

javascript - 我正在努力展平一个对象中的两个数组

c# - 如何将 Int[][] 转换为 Double[][]?

java - 为什么我会得到 NullPointerException?

c - 无法将数组值写入内存

java - n位二进制排列表示的时间复杂度