从最常出现的图中获取 y 值之一的最快方法是什么？我只有本地的最高值和最低值。我只需要一个(随机的)y 值。
例如，如果我有这样的图表:
最常见的 y 值可以是 0 或 1(正如我所说，我只需要一个)。
谢谢。
最佳答案
考虑一条从底部移动到顶部的水平扫描线。最初，它遇到图形 0 次。如果它越过最小值，它就会比以前多两倍地开始接触曲线。如果它超过最大值，它就会开始减少两倍的曲线。如果遇到端点，它会开始多一次或少一次满足曲线，具体取决于它旁边的点的类型。
实际上，最小值和最大值是交替出现的，因此您只需查看局部极值的奇偶校验即可判断增量。
因此您可以通过将极值与增量一起排序来找到解决方案。
Extrema/increments
0 2 -2 6 0
+1 -2 +2 -2 +1
Sorted extrema/increments
-2 0 0 2 6
+2 +1 +1 -2 -2
Number of intersections (prefix sum of the increments)
0 2 3 4 2 0
关于algorithm - 图中最常见的 y 值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23041566/