forループ内の2つの符号付き整数を比較する奇妙な動作

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、 5]、[7,10]。ポイントのカバレッジを計算

• 3座標1で点、6、および11

  ：

• 座標点1と、

  0〜5は、計算を終了します！第一の点について

  カスタムチェック：

• （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：座標[-10、10]と

• 1セグメント。
ポイントのカバレッジを計算

• 3座標-100における点、100、および10

  ：

  計算を終えました！

  カスタムチェック：

• は（-10 < = 0と0 < = 10）ですか？真

あなたが見ることができるように、内側ループの条件が何らかの形セグメントに対して、座標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

big-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では、あなたはとends[i] == 10ので、内部ループ（i==0とj==1）の第2回の反復でループのため終了します。ループを終了したので、0は決してチェックされません。

forループを入力する前に、pointsをソートしてみてください。