0

我正在尝试解决如下所述的问题：给定一组段和一组点，计算每个点包含多少段。

我遇到的问题是当我必须计算一个点被段包含多少次时。当我有某个输入时，内部循环会正确递增每个点的计数器，当我有另一个数据集时，天气会比较零与负数和非负数，它的行为很奇怪。

以下只是为了定位我面临的问题而创建的脚本，并不代表实际的实现。

测试用例给出如下输出：

情况1：

    String debug = "Test case 1: \n ";
    debug += " \n - 2 Segments with coordinates [0, 5] and [7, 10].";
    debug += " \n - 3 points at the coordinates 1, 6, and 11.";
    int [] starts = new int[]{0, 7};
    int [] ends = new int[]{5, 10};
    int [] points = new int[]{1, 6, 11};

    debug += "\n \n Calculating the coverage of the points: ";
    for ( int i=0; i<starts.length; i++) {
        for (int j=0; j<points.length && ( starts[i] <= points[j] && points[j] <= ends[i]); j++) {
            debug += " \n * Point with coordinate " + points[j] + ", is between " + starts[i] + " and " + ends[i];
        }
    }
    debug += "\n \n FINISHED the calculation!";

    int start = 0, point = 1, end = 5;
    debug += "\n \n Custom check for the 1st point: ";
    debug += "\n - Is (" + start + " <= " + point + " and " + point + " <= " + end + ")? " + ( start <= point && point <= end );
    System.out.println(debug);

输出：

测试用例 1：

  • 2 个坐标为 [0, 5] 和 [7, 10] 的段。

  • 坐标 1、6 和 11 处的 3 个点。

    计算点的覆盖范围：

  • 坐标为 1 的点在 0 到 5 之间

    完成计算！

    自定义检查第 1 点：

  • 是（0 <= 1 和 1 <= 5）吗？真的

案例二：

    String debug = "Test case 2: \n ";
    debug += " \n - 1 Segment with coordinates [-10, 10].";
    debug += " \n - 3 points at the coordinates -100, 100, and 10.";
    int [] starts = new int[]{-10};
    int [] ends = new int[]{10};
    int [] points = new int[]{-100, 100, 0};

    debug += "\n \n Calculating the coverage of the points: ";
    for ( int i=0; i<starts.length; i++) {
        for (int j=0; j<points.length && ( starts[i] <= points[j] && points[j] <= ends[i]); j++) {
            debug += " \n * Point with coordinate " + points[j] + ", is between " + starts[i] + " and " + ends[i];
        }
    }
    debug += "\n \n FINISHED the calculation!";

    int start = -10, point = 0, end = 10;
    debug += "\n \n Custom check: ";
    debug += "\n - Is (" + start + " <= " + point + " and " + point + " <= " + end + ")? " + ( start <= point && point <= end );
    System.out.println(debug);

输出：

测试用例 2：

  • 1 段坐标为 [-10, 10]。

  • 坐标 -100、100 和 10 处的 3 个点。

    计算点的覆盖范围：

    完成计算！

    自定义检查：

  • 是（-10 <= 0 和 0 <= 10）吗？真的

如您所见，内部循环的条件在某种程度上没有正确计算坐标为 0 的点相对于段 [-10, 10] 的情况。

在此先感谢，恩德里特。

4

2 回答 2

0

您的问题在于您的for循环条件：

for (int j=0; j<points.length && ( starts[i] <= points[j] && points[j] <= ends[i]); j++) {

一旦您遇到任何point[j]不介于两者之间的内容starts[i]，ends[i]然后循环将终止，您将不会检查任何后续点。

相反，您应该将循环条件与交集条件分开。在伪代码中：

for every (start, end) pair:
    for every point:
         if point intersects (start, end):
              increment counter
         otherwise continue to next point

那有意义吗？

于 2016-11-05T19:10:26.503 回答
0

要减少points.Length*的大 O 顺序ends.Length，您可以同时遍历两者。我假设段不能重叠。

Array.sort(starts);
Array.sort(ends);
Array.sort(points);
int pointIndex = 0;
String debug = ""
int numCollisions = 0;
bool collides = False;
for (int i=0; i < ends.length; i++) {
    debug += "Points between " + starts[i] + " and " + ends[i] ":\n";
    while (pointIndex < points.Length && points[pointIndex] < starts[i]) {
        pointIndex++;
    }
    while (pointIndex < points.Length && points[pointIndex] <= ends[i]) {
        numCollisions++;
        debug += "    " + points[pointIndex] "\n";
        pointIndex++;
    }
}
debug += "Total number of collisions: " + numCollisions;
System.out.println(debug);

// 原始响应：

在测试用例 2 中，您在内部循环 ( i==0and j==1) 的第二次迭代中退出 for 循环，因为points[j] == 100and ends[i] == 10. 由于您已退出循环，因此永远不会检查 0。

points在进入 for 循环之前尝试排序。

于 2016-11-05T19:15:43.843 回答