时间戳

首页 > 解决方案 > 如何快速找到给出最大值的点？请使用 Java 或 C++ 代码

java - 如何快速找到给出最大值的点？请使用 Java 或 C++ 代码

问题描述

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

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) 的时间复杂度

标签： javac++mathgeometrylinear-programming

解决方案

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

考虑价值函数v(x)，然后考虑它的离散导数dv(x)=v(x)-v(x-1)。假设你只有一个区间，比如说{3,3}。dv(x) 是从 -infinity 到 -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数据在哪里

推荐阅读