for 루프에서 부호있는 정수 두 개를 비교하는 이상한 동작

Question

다음과 같이 문제를 풀려고합니다. 설정된 세그먼트와 점 집합이 있으면 각 점을 포함하는 세그먼트 수를 계산합니다.

내가 만난 문제는 세그먼트에 포인트가 몇 번 포함되어 있는지 계산해야하는 경우입니다. 특정 입력이있는 경우 내부 루프가 올바르게 각 포인트의 카운터를 증가시키고 다른 데이터 세트가있는 경우 날씨가 음수와 음수가 아닌 영을 비교할 때 이상하게 작동합니다.

다음은 내가 직면하고있는 문제를 찾기 위해 작성된 스크립트이며 실제 구현을 나타내지는 않습니다. ,

• 2 세그먼트 좌표 [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

  테스트 케이스는 다음과 같은 출력을 제공 5], [7, 10]. 포인트의 커버리지 계산

• 3 좌표 1, 6에서 지점 및 제

  1 좌표와

• 포인트,

  0에서 5 사이의 계산을 완료! 1 포인트

  사용자 정의 검사 :

• (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

내부 루프의 조건은 세그먼트 [-10, 10]에 상대적인 좌표가 0 인 점의 경우를 적절히 계산하지 못합니다.

미리 감사드립니다. 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]가 발생한다.

대신 루프 조건과 교차 조건을 분리해야합니다. 의사 코드 :

의미가 있습니까?

Answer 2

큰 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)의 두 번째 반복에서 루프의 종료. 루프를 종료 했으므로 0은 확인되지 않습니다.

for 루프를 입력하기 전에 points을 정렬 해보십시오.