gần nhất cặp tiền trong hai mảng được sắp xếp

Question

Với hai mảng sắp xếp các số nguyên, a và b, và một số nguyên c, tôi phải tìm i,j ví dụ rằng:

a[i] + b[j] <= c 

và a[i] + b[j] là lớn càng tốt.

Giải pháp tốt nhất mà tôi có thể nghĩ đến là trong O ( n log n) thời gian, lấy mỗi số nguyên từ mảng đầu tiên và tìm giá thấp hơn ràng buộc của "c-a[i]".
Bất cứ ai có thể gợi ý cho tôi cách tốt hơn để làm điều này (có thể trong thời gian O ( n))?

Answer 1

Suy nghĩ một chút về nó, sau đó bạn có thể tự hỏi mình:
"Mỗi lần tìm kiếm trong mảng b được sắp xếp cho các giá trị kế tiếp từ []?"

Answer 2

Tôi nghĩ bạn không phải tìm kiếm toàn bộ mảng b [] lần sau ....... u phải tìm kiếm ở giữa bắt đầu của mảng b và u bị ràng buộc thấp nhất được tìm thấy cho đến bây giờ .... cho yếu tố tiếp theo trong một []. Nó chắc chắn sẽ làm giảm thời gian phức tạp của bạn ... và khi bạn tìm thấy mục tiêu đã cho 'c' bạn phải ngừng tìm kiếm của bạn.

Answer 3

Các giải pháp dưới đây là ở tuyến tính Thời gian phức tạp O (n), Space phức tạp O (1)

public class ClosestPair { 

    public static void main(String[] args) 
    { 
     int ar2[] = {4, 5, 7}; 
     int ar1[] = {10, 20, 30, 40}; 
     int x = 10 ; 
     closest(ar1,ar2,x); 
    } 
    public static void closest(int[] ar1, int[] ar2, int x) 
    { int diff=Integer.MAX_VALUE; 
     int first_num=0; 
     int second_num=0; 
     int second_diff=Integer.MAX_VALUE; 
     for(int i=0; i<ar1.length; i++) 
     { 
      if(x==ar1[i]) 
      { 
       System.out.println("no pair possible"); 
       return; 
      } 
     } 
     for(int i=0; i<ar2.length; i++) 
     { 
      if(x==ar2[i]) 
      { 
       System.out.println("no pair possible"); 
       return; 
      } 
     } 
     for(int i=0; i<ar2.length; i++) 
     { 

      if(Math.abs(x-ar2[i])<=diff) 
      { 
       diff=Math.abs(x-ar2[i]); 
       first_num=ar2[i]; 
      } 
     } 
     diff=x-first_num; 
     for(int i=0; i<ar1.length; i++) 
     { 
      if(Math.abs(diff-ar1[i])<=second_diff) 
      { 
       second_diff= Math.abs(diff-ar1[i]); 
       second_num= ar1[i]; 
      } 
     } 
     System.out.println(first_num + " "+ second_num); 
    } 
}