¿Busca el elemento máximo que es común en dos matrices?

Question

Dadas dos matrices, ¿cómo encontrar el elemento máximo que es común a ambas matrices?

Estaba pensando en ordenar las matrices (n log n) y luego realizar la búsqueda binaria de cada elemento de una matriz ordenada (empezando por una más grande) en otra matriz hasta que se encuentre la coincidencia.

por ejemplo:

a = [1,2,5,4,3] 
b = [9,8,3] 

Maximum common element in these array is 3 

¿Podemos hacer algo mejor que log n n?

Answer 1

Con un poco de espacio extra, puede hacer hash en 1 matriz, luego hacer un contenedor en cada elemento de la otra matriz, manteniendo un registro del mayor valor que devuelve verdadero. Sería O (n).

Answer 2

Puede usar el espacio O(N).
Simplemente ve a través del primer conjunto y coloca todos los elementos en un HashTable. Esto es O(N)
Luego vaya a través de la segunda matriz manteniendo un registro del máximo actual y verificando si el elemento está en el HashTable. Esto también es O(N). tiempo de ejecución Así total es O(N) y O(N) espacio adicional para el Ejemplo HashTable

en Java:

public static int getMaxCommon(int[] a, int[] b){ 
    Set<Integer> firstArray = new HashSet<Integer>(Arrays.asList(a)); 
    int currentMax = Integer.MIN_VALUE; 
    for(Integer n:b){ 
    if(firstArray.contains(n)){ 
     if(currentMax < n){ 
       currentMax = n 
     } 
    } 
    } 
    return currentMax; 
} 

Answer 3

Si bien depende de la complejidad de tiempo de las diversas operaciones en idiomas específicos, ¿qué hay de la creación de conjuntos de las matrices y encontrar el valor máximo en la intersección de los dos conjuntos? Pasando por las complejidades del tiempo para las operaciones en Python, sería, en promedio, O (n) para las asignaciones establecidas, O (n) para las intersecciones, y O (n) para encontrar el valor máximo. Entonces, el caso promedio sería O (n).

¡Sin embargo! El peor de los casos sería O (len (a) * len (b)) -> O (n^2), debido a la complejidad del tiempo del peor caso de las intersecciones establecidas.

Más información aquí, si usted está interesado: http://wiki.python.org/moin/TimeComplexity

Answer 4

Si ya conoce el rango de números que estén en sus matrices, puede realizar contando especie, y luego realizar la búsqueda binaria como usted quería. Esto produciría O (n) tiempo de ejecución.

Answer 5

Pseudocódigo:

sort list1 in descending order 
sort list2 in descending order 
item *p1 = list1 
item *p2 = list2 
while ((*p1 != *p2) && (haven't hit the end of either list)) 
    if (*p1 > *p2) 
    ++p1; 
    else 
    ++p2; 
// here, either we have *p1 == *p2, or we hit the end of one of the lists 
if (*p1 == *p2) 
    return *p1; 
return NOT_FOUND; 

Answer 6

No es un ideal, sino una solución simple, O (len (matriz1) + len (matriz2))

import sys 


def find_max_in_common(array1, array2): 
    array1 = set(array1) 
    array2 = set(array2) 

    item_lookup = {} 

    for item in array1: 
     item_lookup[item] = True 

    max_item = -sys.maxsize 

    intersection = False 

    for item in array2: 
     if not item_lookup.get(item, None): 
      continue 
     else: 
      intersection = True 
      if item > max_item: 
       max_item = item 

    return None if not intersection else max_item 

No