più vicina coppia somma in due matrici ordinate

Question

Date due matrici ordinate di interi, a e b, e un intero c, devo trovare i,j tale che:

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

e a[i] + b[j] è più grande possibile.

La soluzione migliore che posso pensare è in O ( n registro n) tempo, prendendo ogni numero intero da primo array e trovare il limite inferiore di "c-a[i]".
Qualcuno può suggerirmi un modo migliore per farlo (forse nel tempo O ( n))?

Answer 1

Pensandoci un po ', allora potresti chiederti:
"È necessario, ogni volta, cercare nell'array b ordinato per valori successivi da un []?"

Answer 2

Penso che non devi cercare l'intero array b [] la prossima volta ....... devi cercare tra l'inizio dell'array b e il limite inferiore trovato fino ad ora .... per il next element in a []. Ridurrebbe sicuramente la tua complessità temporale ... e quando trovi il dato target 'c' devi interrompere la tua ricerca.

Answer 3

La soluzione qui di seguito è lineare complessità temporale O (n), Spazio Complessità 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); 
    } 
}