比较for循环中两个有符号整数的奇怪行为

Question

我想解决一个问题，如下所示：给定一个集合段和一组点，计算每个点包含多少个段。

我遇到的问题是当我不得不计算一个点包含点的次数时。当我有一个确定的输入时，内部循环会正确地递增每个点的计数器，当我有另一个数据集时天气正常，将零与负数进行比较并发生非负数，它会表现得很奇怪。

以下只是一个脚本，用于查找我面临的问题，并不代表实际的实施。

测试用例得到输出如下：

情况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,1 5]和[7,10]。

• 3点在坐标1,6和11

  计算的点的范围内：

• 点与坐标1，是0-5

  FINISHED计算！

  为第一点定制检查：

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

情况2：

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]。

• 3点的坐标-100，100和10

  计算点的覆盖范围：

  完成计算！

  定制检查：

• 是（-10 < = 0和0 < = 10）？ true

正如您所看到的，内部循环的条件在某种程度上不适合计算坐标为0的点相对于段[-10，10]的情况。

在此先感谢， Endrit。

Answer 1

你的问题是在你for循环条件：

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

只要你遇到不starts[i]和ends[i]之间说谎point[j]则循环将终止，您将不检查任何后续点。

而应将环路条件与交叉条件分开。伪代码：

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

这是否有意义？

Answer 2

要减少来自points.Length * ends.Length的big-O订单，您可以同时循环访问两者。我假设分段不能重叠。

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，你退出for循环的内环（i==0和j==1），因为和ends[i] == 10的第二个迭代。既然你已经退出循环，那么0永远不会被检查。

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