如何快速找到给出最大值的点？ Java 或 c++ 代码

Question

我需要一种快速的方法来在间隔重叠时找到最大值，这与查找重叠最多的点不同，这里有“顺序”。我会 int[][] data int[] 中的 2 个值，其中第一个数字是中心，第二个数字是半径，离中心越近，该点的值就越大.例如，如果我得到如下数据：

int[][] data = new int[][]{
{1, 1},
{3, 3},
{2, 4}};

然后在数字轴上，这就是它的样子：

x axis: -2 -1 0 1 2 3 4 5 6 7  
   1 1:       1 2 1  
   3 3:       1 2 3 4 3 2 1  
   2 4:  1  2 3 4 5 4 3 2 1

因此，为了使我的点的值尽可能大，我需要选择点 x = 2，它给出的总值为 1 + 3 + 5 = 9，这是可能的最大值。有办法快速做到吗？像 O(n) 或 O(nlogn)

的时间复杂度

Answer 1

嗯，一般的 O(n log n) 或更好会很棘手，可能可以通过线性规划解决，但这可能会变得相当复杂。

经过一番争论，我认为这可以通过线交点和函数求和（由线段交点表示）来解决。基本上，将每个视为一条线上的三角形。如果输入为 (C,R) 三角形以 C 为中心，半径为 R。线上的点是 C-R (value 0)、C (value R) 和 C+R (value 0)。三角形的每条线段代表一个值。

考虑任意 2 个这样的“三角形”，最大值出现在两个位置之一：

其中一个三角形的顶点
三角形的交点或两个三角形的交点。多个三角形只是意味着更多可能的交点，遗憾的是可能的交点数量呈二次方增长，因此使用此方法可能无法实现 O(N log N) 或更好（除非找到一些好的优化），除非交点数量为 O(N) 或更少。

要找到所有交点，我们可以使用标准算法，但我们需要以一种特定的方式进行修改。我们需要添加一条从每个峰延伸到足够高的线，这样它就会高于任何一条线，所以基本上是从 (C,C) 到 (C,Max_R)。然后我们运行算法，输出敏感的交集查找算法是 O(N log N + k) 其中 k 是交集的数量。遗憾的是，这可能高达 O(N^2)（考虑 (1,100), (2,100),(3,100)... 的情况，依此类推 (50,100)。每条线都会与其他线相交。一旦有了 O(N + K) 交点。在每个路口，您可以通过对队列中的所有点求和来计算值。运行宁总和可以作为缓存值保存，因此它只更改 O(K) 次，尽管这可能不可能，在这种情况下，它会 O(N*K) 代替。使其成为潜在的 O(N^3)（在最坏的情况下 K）代替 :(。虽然这看起来很合理。对于每个交叉路口，你需要总结 O(N) 行以获得该点的值，但在实践中，它可能会更好。

考虑到您的目标是最大化而不只是寻找交点，可以进行一些优化。可能有不值得追求的交叉路口，但是，我也可以看到它非常接近以至于无法将其切断的情况。让我想起了凸包。在许多情况下，您可以轻松减少 90% 的数据，但在某些情况下，您会看到最坏的结果（每个点或几乎每个点都是一个外壳点）。例如，在实践中肯定有一些原因可以确定总和将小于当前已知的最大值。

另一个优化可能是构建区间树。

Answer 2

这可以通过简单的 O(n log n) 算法来完成。

考虑价值函数v(x)，然后考虑它的离散导数dv(x)=v(x)-v(x-1)。假设你只有一个间隔，比如 {3,3}。 dv(x) 从-无穷大到-1 是 0，然后从 0 到 3 是 1，然后是从 4 到 6 是 -1，然后是从 7 到无穷大是 0。也就是说，导数“刚好在”-1 之后变化 1，刚好在 3 之后变化 -2，刚好在 6 之后变化 1。

对于n个区间，有3*n个导数变化（其中一些可能发生在同一点）。所以找到所有衍生变化的列表 (x,change)，按它们的 x 对它们进行排序，然后遍历集合。

看：

intervals = [(1,1), (3,3), (2,4)]

events = []
for mid, width in intervals:
    before_start = mid - width - 1
    at_end = mid + width
    events += [(before_start, 1), (mid, -2), (at_end, 1)]

events.sort()

prev_x = -1000
v = 0
dv = 0

best_v = -1000
best_x = None

for x, change in events:
    dx = x - prev_x
    v += dv * dx
    if v > best_v:
        best_v = v
        best_x = x
    dv += change
    prev_x = x

print best_x, best_v

还有 java 代码：

 TreeMap<Integer, Integer> ts = new TreeMap<Integer, Integer>();
        
    for(int i = 0;i<cows.size();i++) {
        int index = cows.get(i)[0] - cows.get(i)[1];
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) + 1);
        }else {
            ts.put(index, 1);
        }
            
        index = cows.get(i)[0] + 1;
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) - 2);
        }else {
            ts.put(index, -2);
        }
            
        index = cows.get(i)[0] + cows.get(i)[1] + 2;
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) + 1);
        }else {
                ts.put(index, 1);
        }
    }
        
    int value = 0;
    int best = 0;
    int change = 0;
    int indexBefore = -100000000;
        
    while(ts.size() > 1) {
        int index = ts.firstKey();
        value += (ts.get(index) - indexBefore) * change;
        best = Math.max(value, best);
        change += ts.get(index);
        ts.remove(index);
    }

其中 cows 是数据

如何快速找到给出最大值的点？ Java 或 c++ 代码

How to find the point that gives the maximum value fast? Java or c++ code please

java

c++

math

geometry

linear-programming