0

我正在尝试用 Java 解决以下问题（尽管它可以用几乎任何其他语言完成）：

我得到了两个整数值数组，xs和ys，表示 x 轴上的数据点。它们的长度可能不相同，尽管两者都 > 0，并且它们不需要排序。我要计算的是两个数据集点之间的最小距离度量。我的意思是，对于每一个我都在集合中x找到最近的并计算距离，例如。例如：yys(x-y)^2

xs = [1,5]
ys = [10,4,2]

应该返回 (1-2)^2 + (5-4)^2 + (5-10)^2

距离测量并不重要，它是我感兴趣的算法。我正在考虑以某种方式对这两个数组中的数组和高级索引进行排序，以实现比蛮力更好的效果（对于 x 中的每个元素，扫描 ys 中的所有元素以找到min) 即O(len1 * len2).

这是我自己正在解决的问题，而不是作业问题。您的所有提示将不胜感激。

4

3 回答 3

2

我假设 HighPerformanceMark （对您的问题的第一条评论）是正确的，并且您实际上采用了较大的数组，为每个元素找到较小数组中最接近的一个，并在这些距离上总结一些 f(dist)。

我会建议你的方法：

Sort both arrays 
indexSmall=0 

// sum up
for all elements e in bigArray {
  // increase index as long as we get "closer"
  while (dist(e,smallArray(indexSmall)) > dist(e,smallArray(indexSmall+1)) {
    indexSmall++
  }
  sum += f(dist(e,smallArray(indexSmall)));
}

这是O(max(len1,len2)*log(max(len1,len2)))为了排序。其余的与较大的数组长度成线性关系。现在dist(x,y)将类似于abs(x-y), 和f(d)=d^2或任何你想要的东西。

于 2012-06-11T13:48:29.280 回答
1

您的方法非常好，并且具有O(n1*log(n1)+n2*log(n2))时间复杂度。

如果数组的长度不同，另一种方法是：

  1. 对较短的数组进行排序；
  2. 从头到尾遍历较长的数组，使用二分查找在已排序的短数组中定位最近的项目。

这具有O((n1+n2)*log(n1))时间复杂度，其中n1是较短数组的长度。

于 2012-06-11T13:37:09.830 回答
1

你提出的想法对我来说听起来不错。您可以在 O(n logn) 时间内对列表进行排序。然后，您可以使用另一个上的滑动索引对更长的列表进行一次迭代以找到“对”。随着您在更长的列表中前进，您将永远不必回溯另一个。所以现在你的整个算法是 O(n logn + n) = O(n logn)。

于 2012-06-11T13:31:52.203 回答