2

给定：A[1..n]实数数组。

目标：一个数组D[1..n]，使得

D[i] = min{ distance(i,j) : A[j] > A[i] }

或者当没有更高值的元素时使用一些默认值（如 0）。我真的很想在这里使用欧几里得距离。

示例：

A = [-1.35, 3.03, 0.73, -0.06, 0.71, -0.21, -0.12, 1.49, 1.41, 1.42]
D = [1, 0, 1, 1, 2, 1, 1, 6, 1, 2]

有什么办法可以打败明显的 O( n^2) 解决方案？到目前为止，我取得的唯一进展是D[i] = 1无论何时A[i]都不是局部最大值。我一直在想很多，并没有想出任何东西。我希望最终将其扩展到二维（矩阵也是如此）A。D

4

2 回答 2

1

所以我对此有点困惑，但我还没有想出更好的方法。一些想法：

  • 使用可以在 O(n) 时间或更短的时间内获得的额外信息来增强数组。例如，添加索引、邻居之间的差异等。
  • 排序 (O(n(log n)) 有什么帮助吗？
  • 似乎动态编程在这里可能会有所帮助，如果您可以找到一种基于其邻居的解决方案来解决每个元素的方法（使用诸如jfor each之类的信息来增加答案，A[i]而不仅仅是距离）。
于 2010-04-01T14:23:43.460 回答
0

将数组从最高元素到最低元素排序。如果我正确理解了您的问题，这将立即为您提供答案，因为与原始列表中任何元素最接近的较大元素是它之前的元素。这样，您甚至不需要创建 D[] 数组，因为其内容的计算可以仅使用数组 A[] 来完成。排序后的 A[] 数组中的第一个元素没有更大的朋友，因此它的答案将是您的默认值（也许是 0？）。扩展矩阵的算法可能很容易（取决于你如何“看待”矩阵）——只需使用一个映射函数，它可以将矩阵转换为一维数组。

于 2010-05-27T06:01:07.480 回答