O (log (n)) 시간 간격으로 계산하십시오.

Question

나는 trip_beginning과 trip_end 간격의 두 배열을 가지고 있습니다. trip_beginning [j] trip_end [j] j 번째 간격의 끝과 시작을 나타냅니다. 배열 M 및 S가 정렬됩니다.

S가 색인을 포함하고 있으면 trip (badTrip)을 필터링해야하며, badTrip이 아닌 경우 해당 간격의 M 색인 수를 계산해야합니다. 마지막에 maxCt 카운트 (tripMax)의 트립이 이깁니다.

코드가 올바른 결과를 반환하지만 점근적으로 빠를 필요가 있습니다. 이러한 경우가 루프 T의 * (로그 (M + S). 때문에 중. 는 간 간격 (포함. 엔드 포인트) 비교를 할 수있는 빠른 방법이있는가요?

int tripMax = 0; 
int maxCt = Integer.MIN_VALUE; 

for (int j=0; j< trip_beginning.length; j++){ 
    int tripNo = j+1; 
    boolean badTrip = false; 
    int tripS = trip_beginning[j]; 
    int tripE = trip_end[j]; 
    int mountains = 0; 


     for (int k=tripS; k <= tripE; k++){ 
      if (Bsearch(S,k)==1){ 
       badTrip= true; 
       // break; 
      } 
      if (!badTrip && Bsearch(M,k)==1){ 
        mountains++; 
      } 

     } //endfor 


    if (!badTrip && (mountains>maxCt)){ 
     maxCt = mountains; 
     tripMax = tripNo; 

    } 

Answer 1

당신 바이너리 검색은 trip_beginning [j]와 trip_end [j] + 1의 두 값에 대해서만 이진 검색을 수행해야하며, 이진 검색은 해당 값이 검색 할 숫자보다 작은 최대 인덱스를 찾아야합니다 (배열의 첫 번째 숫자보다 작거나 같으면 -1) 여행의 두 끝 사이의 색인 차이를 계산합니다 .S의 경우 색인 차이가 0이 아닌 경우 S의 일부 요소가 두 끝 사이에 있고, 그러므로 나쁜 여행 .M의 경우 지수 차이는 산의 수입니다. (n (log | S | + log | M |)) 시간.