对于每个元素A [i]于阵列A的，找到最接近Ĵ使得A [J]> A [I]

鉴于：实数的数组A[1..n]。对于每个元素A [i]于阵列A的，找到最接近Ĵ使得A [J]> A [I]

目标：数组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]不是本地最大值。我一直在想很多，并没有提出什么。我希望最终扩展到2D（所以A和D是矩阵）。

来源

2010-03-31 SamH

你的符号很好很简洁，但如果你用英文解释的话，它可能会更有用（你可能会得到更多的答案）。 – noah 2010-03-31 20:08:24

需要'家庭作业'标签？ – 2010-03-31 21:08:31

noah：谢谢！我试图用较少的符号来书写标题，但是当我将它呈现给坐在我旁边的两个人时，他们不喜欢它。我能想到的最好的结果是“在数组的每个元素上，找到最接近数组的元素。” Paul R：这实际上是我正在研究的一个更大项目中的一小部分，这不是作业。但你是对的，它看起来像功课。 – SamH 2010-03-31 21:32:04

所以我对这一点感到困惑，但我还没有拿出任何更好的作品。一些想法：

增加阵列与额外的信息，可以在O（n）时间或更好的时间获得。例如添加索引，邻国之间的差异等
将排序（O（N（log n）的）帮助以任何方式？
好像dynamic programming可帮助在这里，如果你能想出一个办法来解决基于其邻居溶液（增强的答案与像j每个A[i]，而不是仅仅是可能的距离信息）的每个元素。

来源

2010-04-01 14:23:43 noah

谢谢，我以前没有想到你的第一个建议。如果我想出任何东西，我肯定会更新此页面！ – SamH 2010-04-02 19:38:04

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

来源

2010-05-27 06:01:07 PeterK

对于每个元素A [i]于阵列A的，找到最接近Ĵ使得A [J]> A [I]

回答

相关问题