Encontrar elementos comunes en dos arreglos de diferente tamaño

Este equipo especializado pasados algunos días de investigación y de juntar de datos, hallamos los datos necesarios, esperamos que resulte de utilidad en tu trabajo.

Solución:

Ordenar las matrices. Luego itere a través de ellos con dos punteros, siempre avanzando el que apunta al valor más pequeño. Cuando apuntan a valores iguales, tienes un valor común. Será O(n log n+m log m) donde n y m son los tamaños de las dos listas. Es como una fusión en el ordenamiento por fusión, pero donde solo produce resultados cuando los valores a los que se apunta son iguales.

def common_elements(a, b):
  a.sort()
  b.sort()
  i, j = 0, 0
  common = []
  while i < len(a) and j < len(b):
    if a[i] == b[j]:
      common.append(a[i])
      i += 1
      j += 1
    elif a[i] < b[j]:
      i += 1
    else:
      j += 1
  return common

print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

salidas

Common values: 1, 4

Si los elementos no son comparables, coloque los elementos de una lista en un mapa hash y compare los elementos de la segunda lista con el mapa hash.

Si quieres que sea eficiente, convertiría el más pequeño array en un hashset y luego iterar el más grande array y verifique si el elemento actual estaba contenido en el hashset. La función hash es eficiente en comparación con la clasificación de matrices. Ordenar arreglos es costoso.

Aquí está mi código de muestra

import java.util.*;
public class CountTest      
    public static void main(String... args)         
        Integer[] array1 = 9, 4, 6, 2, 10, 10;
        Integer[] array2 = 14, 3, 6, 9, 10, 15, 17, 9;                    
        Set hashSet = new HashSet(Arrays.asList(array1)); 
        Set commonElements = new HashSet();        
        for (int i = 0; i < array2.length; i++) 
            if (hashSet.contains(array2[i])) 
                commonElements.add(array2[i]);
            
        
        System.out.println("Common elements " + commonElements);
        

Producción:

Elementos comunes [6, 9, 10]

Tira tu A2 array en un HashSet, luego iterar a través de A1; si el elemento actual está en el conjunto, es un elemento común. Esto toma O(m + n) tiempo y O(min(m, n)) espacio.

Si eres capaz, tienes la habilidad dejar un ensayo acerca de qué te ha impresionado de este ensayo.

---

---

Utiliza Nuestro Buscador