对于数组A的每个元素A[i]，找到最接近的j使得A[j]>人工智能]
给定：实数数组A[1..n]。
该数组
D[i] = min{ distance(i,j) : A[j] > A[i] }
目标：一个数组D[1..n] ，当没有更高值的元素时， 或某个默认值（如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) 解决方案吗？到目前为止，我取得的唯一进展是，每当 A[i] 不是局部最大值时，D[i] = 1 。我想了很多却什么也没想出来。我希望最终将其扩展到二维（因此 A 和 D 是矩阵）。
Given : An array A[1..n] of real numbers.
Goal : An array D[1..n] such that
D[i] = min{ distance(i,j) : A[j] > A[i] }
or some default value (like 0) when there is no higher-valued element. I would really like to use Euclidean distance here.
Example :
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]
Is there any way to beat the obvious O(n^2) solution? The only progress I've made so far is that D[i] = 1 whenever A[i] is not a local maxima. I've been thinking a lot and have come up with NOTHING. I hope to eventually extend this to 2D (so A and D are matrices).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
所以我对此有点困惑，但我还没有想出任何更好的方法。一些想法：
j 对于每个A[i]而不仅仅是距离）。So I've puzzled on this a bit but I haven't come up with anything better that works. A few ideas:
jfor eachA[i]instead of just the distance maybe).将数组从最高元素到最低元素排序。如果我正确理解你的问题，这会立即给你答案，因为与原始列表中任何元素最接近的较大元素是它之前的元素。这样，您甚至不需要创建 D[] 数组，因为可以专门使用数组 A[] 来计算其内容。排序后的 A[] 数组中的第一个元素没有更大的朋友，因此它的答案将是您的默认值（也许是 0？）。扩展矩阵算法可能很容易（取决于您如何“看待”矩阵） - 只需使用映射函数即可将矩阵转换为一维数组。
Sort the array from highest to lowest element. If I understand your problem correctly, this gives you the answer immediately, since the closest bigger element to any element in the original list is the one before it. This way you don't even need to create the D[] array, since computation of its contents can be done using the array A[] exclusively. The first element in the sorted A[] array does not have a bigger friend so the answer for it would be your default valye ( 0 perhaps?). Extending the algorithm for matrices might be easy (depends on how you "look" at the matrix) - just use a mapping function which sort of transofrms the matrix into a 1D array.