más cercano suma par de dos matrices ordenadas

Question

Dados dos conjuntos ordenados de números enteros, a y b, y un entero c, tengo que encontrar i,j tal que:

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

y a[i] + b[j] es más grande posible.

La mejor solución que puedo pensar es en O ( n registro n) tiempo, teniendo cada número entero de primera matriz y encontrar el límite inferior de "c-a[i]".
¿Alguien puede sugerirme una mejor manera de hacer esto (tal vez en O ( n) tiempo)?

Answer 1

Pensando un poco sobre él, entonces usted podría preguntarse:
"¿Es necesario, cada vez, para buscar en el b-matriz ordenada de valores sucesivos de un []?"

Answer 2

Creo que no tiene que buscar toda la matriz b [] la próxima vez ....... tiene que buscar entre el inicio del conjunto b y el límite inferior encontrado hasta ahora ... para el próximo elemento en a []. Definitivamente reduciría la complejidad de su tiempo ... y cuando encuentre el objetivo dado 'c', debe detener su búsqueda.

Answer 3

La solución a continuación es lineal en el tiempo la complejidad O (n), complejidad espacio 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); 
    } 
}