diferencia absoluta mínima entre dos números en una matriz

Question

Dadas dos matrices, A y B, quiero encontrar un número de A y un número de B, de modo que la diferencia absoluta entre los dos números sea la más pequeña.

Eg

A = 1 2 9 
B= 4 5 6 

Ans: 2,4 como Math.abs (2-4) = 2

Answer 1

Ordenar las dos matrices, a continuación, iterar en paralelo: Para cada elemento en A, búsqueda el elemento más cercano en B mediante una búsqueda lineal. Inicie la búsqueda lineal en B donde se detuvo para el artículo anterior de A. Recuerde siempre la distancia mínima encontrada hasta ahora.

La complejidad del tiempo es O (m log m + n log n) para la clasificación y O (m + n) para la búsqueda final, donde myn son las respectivas longitudes de A y B.

Answer 2

comprobar esto, tal vez le da una idea de lo que adaptarlo a sus necesidades:

#define TOP 2147483647 
#define true 1 
#define false 0 


/* finds the minimum (absolute value) of vector vec */ 

void Vector_Min_Not_0(vector *vec, int *min, int *index) 
{ 
    int m, size, i, ind, aux; 

    size = vec->size; 
    m = TOP; 
    ind = -1; 
    for (i = 0; i < size; i++) 
    if (vec->p[i] != 0) 
     if (m > (aux = abs(vec->p[i]))) { 
    ind = i; 
    m = aux; 
     } 
    if (ind == -1) 
    *min = 1; 
    else 
    *min = m; 
    *index = ind; 
} 

que lo llamarían, tiene una estructura:

typedef struct vector { 
    int size; 
    int *p; 
} vector; 

vector vec_A; 
int min, index, *p; 
Vector_Min_Not_0(&vec_A, &min, &index); 

Answer 3

que se podía hacer en O (nlogm + mlogm) = O (nlogm):
(m es la longitud array`s más pequeño)
asumen B es la matriz más pequeña

sort array B 
minimum = | A[0]-B[0] | 
for each a in A: 
binary search for a in B - return the closest numbers let the numbers be b1,b2 (*) 
if min{|b1-a|,|b2-a|} is smaller then the previous minimum - store it as the new minimum 

(*) binario de búsqueda se detiene cuando se encuentra más cercano al número (o lo encuentra, si es que existe)
antes comprobar que es más pequeña (A o B) asegurará una mejor performance.-

Answer 4

soy haciendo la suposición de que los números en la matriz serán flotantes. En Ruby:

def smaller_abs(array1, array2) 
    array1.product(array2).each_with_index do |ar,i| 
     if i==0 
     dif = (ar[0]-ar[1]).abs 
     pair = ar 
     next 
     end 
     pair = (ar[0]-ar[1]).abs > dif ? pair : ar 
    end 
    pair 
end 

No soy un gurú del algoritmo, pero que deben trabajar (no se han comprobado). Espero que haya ayudado!

Answer 5

1. Ordenar ambas matrices
2. combinar los dos números utilizando algunas etiquetas para diferenciarlos. por ejemplo, A = 1 9 2 B = 5 4 6

Después de la clasificación:

A = 1 2 9 B = 4 5 6

combinan la matriz: C = 1a 2a 4b 5b 6b 9a

Ahora haga una búsqueda lineal y encuentre la diferencia entre los términos consecutivos con etiquetas diferentes. Respuestas: 2a 4b.