比較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。